（應用數學專業(yè)論文）二元域上的線性含錯方程.pdf

摘要 二元域上的線性含錯方程來源于通信領域中信息出錯這一實際問題 本文 擬要討論的是信息傳輸中有較小部分信息出錯時的解決方法 對于這個問題 通常是采用糾錯碼來解決的 而本文在整數分拆理論 線性代數相關理論的 基礎上 試圖采用線性含錯方程來解決這個問題 全文共分為四章 第一章為導論 簡要介紹了線性含錯方程問題產生的背景 以及本文所涉 及到的一些重要概念 第二章給出了線性含錯方程的一類新解法 在介紹排列方陣 整數分拆 以及一類n m 矩陣的遞推分解的基礎上 得出一個重要的結果 定理2 2 2 對于線性含錯方程w x a 的一個解z 必存在有限個行向量 z 勖 z i 使得t l t l 扛 現 伽 z 七 伽 h 這里詹sm o 伽 毛 s 0j n w b e m 且戤 t 1 糾2 一 蠹的維數n r 2 n n r o 1 r 2 芝n 的和為 m m 或m 分別相應于上述對引理2 2 1 中矩陣a 的分解的兩種情形 在第 一種情形下 m 是矩陣a 分解所得最后的行向量b k 的維數 最后給出了一個基于上面方法的算法和求解算例 第三章對線性含錯方程的解集合進行了理論上的討論 用廣義逆的相關理 論闡述了解的結構 第四章討論了在此類方程的解法上引入的 最小二乘法 問題 其本質是 一個在非阿賦值下求其極值的問題 我們通過建立一種2 一a d i c 域上的整數環(huán) 忍到最的映射 得到一些初步的結果 關鍵詞 線性含錯方程 整數分拆理論 非阿賦值 重量 2 l i n e a re r r o re q u a t i o ni sr a i s e db yt h ep r o b l e mo fe r r o r si nt h ep r o c e s so fi n f o r m a t i o nt r a n s m i s s i o n t h i sp r o b l e mi sn s u a i l ys o l v e db yc o d i n gt h e o r ya n de r r o rc o r r e c t i n gt h e o r y b u tn o ww ea t t e m p t t os o l v ei tb yl i n e a re r r o re q u a t i o n w h i c hi sb a s e do nt h et h e o r yo fp a r t i t i o na n dl i n e a ra l g e b r a t h ep a p e ri ss t r u c t u r e di n t of o u rc h a p t e r s c h a p t e r1p r o v i d e sab a c k g r o u n do fl i n e a re r r o re q u a t i o na n di n t r o d u c e ss e v e r a lk e yd e f i n i t i o n s c h a p t e r2p r o v i d e san e wm e t h o dt or e s o l v el i n e a re r r o re q u a t i o n o nt h eb a s i so fa no v e r v i e wo f p e r m u t a t i o nm a t r i x p a r t i t i o nt h e o r ya n dt h es u c c e s s i v ed e c o m p o s i t i o no f l mm a t r i x w ed r a wa n i m p o r t a n tc o n c l u s i o na sf o l l o w i n g t h e o r e m 2 2 2f o ras o l u t i o no fal i n e a re r r o re q u a t i o nw z a b 硼 t h e r ee x i s tf i n i t er o wv e c t o r s z l z 2 z 七s u c ha s 塒 t t c z t t t 坩 f o rk m 0 塒 戤 r w b k m 七a n dt h es 眥o f7 1 r 2 他 ni st h ed i m e n s i o n so f z i 1 2 七 i sm m o rm i nt h ef i r s tc a s e m 女i st h ed i m e n s i o no fb k t h e nw eg i v ea na l g o r i t h ma sw e l la sar e l a t e de x a m p l eb a s e do nt h ep r e v i o u sa n a l y s i s c h a p t e r3h a sad i s c u s s i o na b o u tt h es o l u t i o ns p a c eo fl i n e a re r r o re q u a t i o nw i t ht h et h e o r yo f c h a p t e r4h a sad i s c u s s i o na b o u tt h el e a s ts q u a r em e t h o dt os o l v el i n e a re r r o re q u a t i o n s i nf a c ti t s ap r o b l e mo fe x t r e m u mo v e rn o n a r c h i m e d e a nv a l u a t i o n w eg i v eam a pf r o ma 易o n2 一a d i cf i e l dt o k e y v c o r d s l i n e a re r r o re q u a t i o n p a r t i t i o nt h e o r y n o n a r c h i m e d e a nv a l u a t i o n w e i g h t 聲明尸明 本人鄭重聲明 本人在導師的指導下 獨立進行研究工作所取 得的成果 撰寫成碩士學位論文 二元域上的線性含錯方程 除論 文中已經注明引用的內容外 對本文的研究做出重要貢獻的個人和集 體 均己在文中以明確方式標明 本論文中不包含任何未加注明的其 他個人或者集體已經公開發(fā)表或未公開發(fā)表的成果 本聲明的法律責任由本人承擔 學位論文作者簽名 蘑爻塋凰 2 0 0 3 1 2 1 6 1 導論 1 1 背景介紹 編碼理論起源于現代通信技術與電子計算機技術差錯控制研究的實際需 要 美國數學家香農 a s s h a n n o n 1 9 4 8 年發(fā)表的 通信的數學理論 為現代科學 技術開創(chuàng)了一門嶄新的學科 即信息論 在數字通信系統(tǒng)中 信息傳輸 或存 儲 所面臨的主要問題是在傳輸過程中出現差錯 即傳輸的可靠性問題 數字 通信系統(tǒng)的基本組成如下圖所示 信道編碼的基本思想是根據相關性來檢測和糾正傳輸過程中產生的差錯 香 農在信道編碼定理中指出 在編碼速率小于信道容量的條件下 通過編碼可 以使譯碼錯誤率任意小 從而達到可靠通信的目的 編碼的作用是使信號序 列之間的歐幾里德距離增加 選定一個特定編碼的基本目標有二 其一 用盡可能多的碼字達到較高的編碼效率 即使用盡可能少的冗余度 附加帶寬 其二 使碼字之間的距離越遠越好 這樣 即使矢量在傳輸中受到干擾 它們仍然能以很高的概率被正確的譯碼 2 1 2 線性含錯方程問題的提出 一般在信息傳輸中總會有干擾 當我們編碼成功并發(fā)出信息口 收到的卻可 能是b 這樣的信息傳輸實際上是失敗的 這給我們提出一個很現實的問題 怎樣才能使信息得到成功的傳輸 本文擬要解決的是信息傳輸中有較小部分 信息出錯時的解決方法 假如我們想發(fā)送信息2 釓z z 住 收到的卻是信 息c c c 2 c r i 這里 毛 q 0 i n 且z t q 瑪 收到的z 和c 有較大的差異 即它們的h a m m i n g 距離婦 z c 較大 我們希望解決的是相對于n 來說較小的 差錯 對于這個問題通常是采用糾錯碼理論來解決的 糾錯碼已經發(fā)展了很 多 包括線性碼 h a m m i n g 碼 b c h 碼和代數幾何碼等 本文在整數分拆理 論 線性代數相關理論的基礎上 試圖采用線性含錯方程來解決這個問題 定義1 2 1 設霉為一個n 維的未知行向量 那么我們稱 w z a 6 1 1 為線性含錯方程 這里a 為一個n m 矩陣 b 為一m 維行向量 m n 亦 即m 遠大于n t t 為一個滿足0s 塒sm 的已給定的整數 塒 幸 為幸的重量 1 3 相關概念介紹 擬解決這個問題 我們還需要了解如下幾個基本概念 1 3 1線性碼 線性碼是一類最基本的碼 設日 a f q 是具有q 個元素的有限域 其中q 是一個素數的冪 定義1 3 1 設c 是碼長為n 的q 元碼 即gck 日 碥 日 為日上的n 維線性空 間 如果c 是 日 的子空間 則稱c 為一個口元線性碼 3 假定c 是碼長n 的窖元線性碼 并假定c 是 日 的詹維子空間 那么c 共 含有礦個碼字 并稱c 為一個g 元 n 詹 線性碼 當口 2 時 日 的加法群的 子群一定是子空間 因此 我們可以說如果c 是 足 的加法群的子群 c 就 是二元線性碼 可以把c 看作是原始數字信息集合垓 日 在某一編碼盯 一一映 射 之下的象 口 k 日 一c 設n 維行向量v o 釓 壩一 是c 的一組基 令 g v o 移i 口七一l 那么g 就是日上一秩為詹的老 n 矩陣 因為v o 魄一 是c 的一組基 所以 c 中任一碼字c c o c l c n 一 都可以表示成它們的線性組合而系數屬于蜀 而 且表法是唯一的 c2a o 伽 i n l v l 4 口七一l 饑一1 口 日 i 0 i 七一i 反過來 v o 饑一 的任意一個系數屬于馬的線性組合都是c 中的碼字 實 際上 g 就是c 的一個生成矩陣 利用矩陣乘法 有 c a o 口l 口七一1 g 當然 由線性代數中相關知識我們知道 存在奄x 七可逆陣p 使得g p g 則 g 也是一個生成矩陣 我們可以對g 進行初等變換 將g 化為階梯形矩陣 g o2 4 島中每一行的第一個非零元均為1 分別對應g o 的第i o i h 一 i 列 我們 可以看出 g o 也是c 的一個生成矩陣 g o 的行自上而下記作t 0 0 t t 那么w 0 t t 也是c 的一組基 我們也可以利用g o 對原始數字信息集合 磙 日 進行編碼 盯 口o 口i 1 k 1 a o 口1 口七一1 g o 那么得到的c 中的碼字的第 o i i 位的碼元分別對應原始數字信息的第 o 1 k 一1 位 我們稱第i 0 i 一 一 位為信息位 而其余的位為校驗位 校驗 位的個數為n 一七 當然 我們還可以把g o 進一步化成如下的形式 g o j n p 七加 其中 七 是k 詹單位矩陣 p c h 一d 是日上任一七 n 一七 矩陣 設h 為其校驗 矩陣 令 c z l z k 日 n 0 y a c l 宰 搴 o o o l 0 o 0 0 l 0 0 0 事 0 o o l o 0 事 o o 0 0 0 o l o o 0 o o o o o o 0 o 伊叫做c 的對偶碼 設n 維行向量t i o u h 一 u 一 是伊的一組基 令 u o u l 5 那么h 就是伊的一個生成矩陣 它是日上的一個秩為n k 的機一露 他矩陣 顯然 對任意的z k 日 z c 當且僅當h z 0 這里 我們把n 一七維列向量h z 叫做z 的校驗子 那么z 是d 的一個碼字 當 且僅當z 的校驗子等于n k 維零向量 即h z 0 前述編碼方法在理論上講具有唯一解 可是由于信道有干擾 被接收到的 向量耖可能不等于c 設 e 寥一c e 1 e 2 e n 稱e 為差錯向量 對于g 元 n 知 線性碼c h 是其校驗矩陣 那么k 日 中的兩個字 和 屬于 g 的同一陪集 當且僅當他們的校驗子刪和砌 相等 用校驗子譯碼可以采 用下列步驟 1 給定日上 n j b 線性碼c 的校驗矩陣皿 2 接收信號y 屬于 f 口 3 計算校驗子s h i 4 求出s 對應的陪集 并找出一個最小權向量z o 5 譯成碼字茹 l 一z o 6 1 3 2h a m m i n g 重量和h a m m i n g 距離 定義1 3 2 設z 為一個二元域上的住維行向量 則稱茹的非零分量的個數 為向量z 的海明重量 簡稱為霉的重量 記作塒 茹 對列向量的海明重量可 以同樣定義 下面再介紹一下 乃 上的一種度量 h a m m i n g 距離 令 d h x 耖 圭w u z 比 y k 日 對k 日 中任意二元z 與7 3 他們間的h a m m i n g 距離規(guī)定為不同分量的個數 即 二向量之差的h a i m i n 9 重量 不難驗證 h a m m i n g 距離滿足以下三條性質 對任意的z 掣 k 日 有 a 自反性 婦 z i t 0 2 i t b 對稱性 婦 茁 耖 d n i t z c 三角不等式 d n x i t sd h x 2 d u z i t 1 3 3 最小二乘法 給定一個阿基米德賦值下的線性方程組 用最t 乘法來求得近似解 設 線性方程組 8 1 1 霉i a 1 2 x 2 4 口l m 寫m b x 口2 l z i4 a 2 2 2 24 眈m z m b 2 n n l z l a n 2 x 2 c l m z m 6 n 啦 k r i 1 2 n j l 2 仇 沒有解 令 挑2 一 o k z l4 啦2 勉 啦m z m i 1 2 n 7 如果一組實數 七 k 當 i k t z 2 k 2 z k 時矽 譴 三取得最小 值 可以認為 蠢 如 k 是方程組的最佳近似解 又稱之為該方程組的最小 二乘解 下面討論怎樣來求方程組的最小二乘解 令 a l j a 2 j j 1 2 m a2 將它們看作n 維歐氏空間艫中的向量 再令 6 l 6 2 k w z l a x z 2 a 2 z m n m i z l z 2 z m r 于是g 堙 記就是向量口與w 中任意向量叩 z 口 z n z 口 的距 離 由此可知 當q 與奄l a b q k w 的距離最短時 奄 如 k 就 是所求的最小二乘解 問題便轉化為在 a 生成的子空間w 中求一個 向量 使q 與它的距離是n 與w 的各個向量的距離中最短的 顯然 這個最短的向量就是a 在 內的正射影盧 再求出w 的生成元 口m 的極大無關組 通過正交化和單位化求出 的標準正交基 就可以得到n 在 w 內的正射影盧 由此也不難求出最 i s 乘解 七 k 2 k 不過 按以下方法 會更簡單一些 對z 口 現勉 z q w 來說 它是q 在 內的正射影盧 當 且僅當a 一 z 1 口l z 2 口2 z a 上當且僅當a 一 z l 口l 現q 2 z 口 與彬的生成 元 口2 口 都正交 當且僅當 即 a l lo 2 1 a m t a l l 口2 2 a m 2 h z l a l l z 2 a 1 2 一z m n l m 幻一x l a 2 1 一 霉2 d 2 2 一 z m 口2 m o o b n l x l a n i x 2 a n 2 一z m 口 i m 6 l 6 2 k a z i z 2 蜀m o o o 其中a 是方程組的系數矩陣 由此可知 方程組 a a z l 2 2 z 6 l 6 2 k 0 o o 8 的每一個解都是方程組的最小二乘解 需要說明的是 口在w 內的正射影盧 是唯一的 但是因為口l t a 2 a 可能是線性相關的 所以p 由口l 口2 q 表 出的時候表示法不唯一 從而最小二乘解也不唯一 1 3 4 賦值域 定義1 3 4 設f 為域 函數妒 f 卜 月 o 叫做是域f 的一個賦值 是指滿足如下 3 個條件 對于a b 屬于f 1 妒 口 0 當且僅當口 0 9 2 妒 口6 妒 口 妒 6 3 存在常數c 0 使得 若i i o c a 1 則妒 1 口 m i n v a t 6 1 0 滿足這3 條性質的t 叫做域f 的指數賦值 反過來 給了f 的指數賦值t 則對每個實數7 o y 加 則線性含錯方程 3 3 的通解是 z b g c g 這里g 跑過a 的所有廣義逆 而c 為滿足條件 3 4 的一個固定的m 維行向量 證明 由 6 伽 c 椰 知b c 也即b c 0 設z 為 3 3 的一個解 即存在 滿足 的m 維行向量c 使得 z a b 己 由引理3 2 4 可知 存在a 的廣義逆g 使 z 6 c g b g o g 反之 設存在a 的一個廣義逆g 以及一個滿足 叫 的向量c 使 則存在跏使 以及矩陣u 使 于是 z b g c g 跏a b c g a 一 u a a u a a 一 x a b c g a z o a g a x o a a 一 u a a u a a 一 a o a a a a u a a a a u a a a x o a a u a a u a 加a b c 從而w z a 6 t t c 塒 證畢 42 a d i c 賦值下的極值問題 4 1 在p a d i c 分析上的引人 現在 我們來建立線性含錯方程與p a d i c 分析的聯系 設q 為2 一a d i c 域 即有理數域q 在2 一a d i c 賦值下的完備化域 為了討論 的方便 我們可以這樣做 取q 的代數閉包礪 然后把礪完備化 得到既完 備又代數封閉的域q 這樣凡是涉及到代數方程與取極限 系對2 一a d i c 賦值而 取 均可以在q 中順利進行 設歷為q 2 中的2 一a d i c 整數環(huán) 一般的 如果有理數c a b 2 h k 為整數 口 b 為互素的奇整數 且n o 時 那么c 的2 一a d i c 賦值是 i l c l l 2 2 現在我們繼續(xù)討論線性含錯方程問題 但是注意 這里n m 已經和前面注 記中的交換了 這里n m 設二元域易上元素a i j b 1 i n 1 歹 m 已經給定 現在要求求出使得方 程組 竹t a q x j 6 1 i n 4 1 j x 中等號成立個數最多的z 釓 z m 四 這個問題在實數域或復數域中即在阿基米德賦值下 通常是在最小二乘法 的意義下加以解決的 但是到了有限域 則比較困難了 就是因為有限域只有 顯然賦值 或稱為無聊賦值 我們現在來把 4 1 轉化為下列的2 一a d i c 賦值下的 極值問題 設a o 6 z 2 1si l 1 歹 m 給定 現在要求求出使 n 竹 i i x l i l 圭 叼巧一b d l 1 4 2 取極小值的z z 印 這里j 是一個給定的正整數 它滿足2 t 住 1 先給出 定義4 1 1 作映射 z 2 尼如下 廬 口 a m o d 2 即對于口 是 口蠹2 m o 1 這是忍元素的一般表達式 定義 口 a m o d 2 a o 以下記口在 下的象為石 a 但是我們應該小心引起混亂的地方 易見毋是個環(huán)同態(tài) 4 2 一個初步的結論 定理4 2 1 設z 砑是 4 2 的解 則蠆 即是 4 1 的解 這里 蠆 l m 如z 釓 z 而 4 1 中的叼 阮 均改寫為勘 瓦 毛 證明設z 砑是 4 2 的解 而蠆 四不是問題 4 1 的解 我們來推出一個 矛盾 由解的定義可知問題 4 1 的解可 可 毋 垂2 顯然是有有解的 使 m z 名l 釔 盈 蕊j 乃一瓦 1 i n j r l 的重量塒 名 小于 m w l 鋤 缸h t 以 一a o z j b 1 i n j r l 的重量t t 伽 取y l l 2 跏 易使它們在上述的映射 下的象為礬 m 并置 秒 1 l 拋 耖 這樣 我們有 t z t j t t 一1 w w 1 4 3 又我們有 n竹i i v l l 乞 i l 珊一b l l t o n w c z 1 2 i 1j l 這是因為有伽 名 個i 使 和n 一塒 名 個i 使 還有 今有 這樣用 4 3 可得 m 叼協(xié)一b t 三1 r o o d 2 j l m a t j y j 一6 i 三0 r o o d 2 j 1 n竹i i x l l 乞 l a t j x j 一如 5 伽 t i i 1j 1 w z n 一 0 2 f 1 2 t t t 名 i n 2 t l z i n w z 2 j 1 2 t t l t l 一1 t n 2 一 sw w 一2 w 一1 4 2 t 竹 4 1 伽 t l 一2 w 0 由 4 4 4 5 4 6 即知有 0 z l 工 i i 毫 工 4 4 4 5 4 6 這與z 為 4 3 的解的規(guī)定矛盾 這就證明了蠆是 4 1 的解 并且可知對于上面 定義的名 塒有塒 z t t t t 這點將在下面定理4 2 2 的證明中要用到 定理4 2 2 設對給定的a i j 瓦 1 i n 1sjsm 蠆 霹是 4 1 的解 則存在 z 砑 使得z 為z 在 下的象 且z 是 4 2 的解 除非相應的 4 2 根本沒有解 其中鞏為 在 下的逆象 1 i n a i j 0 l x i n 1 sm 當口 0 1 時 可以 把口與石視為同一的 證明命 m 多二ao而一一 1ci b i1 l n 2 2 而一 l n j l 則c 0 1 局 也可視為a z 2 1 isn 現在歸納地定義 巧 傳 o 1 1 l 竹 l jsm 如下 首先令 于是對t 0 有下式成立 6 l o 瓦 1 i n 鑼 而 1s 歹 m tm 2 口巧 捫一6 5 c m o d 2 1 i 竹 k 0 j l 假定對t 4 1 0 式已經成立 則命 tm 6 l 三2 一 刪 2 毒 一 七 c m o d 2 i i n k 0 j l 于是b 0 1 0 l f 2 也可以視一b 0 l 玩 再取礦1 1 歹 m 使其滿足 m 口蒔母 1 蘭0 m o d 2 1 i n j 1 可視礦1 既屬于b 又屬于忍 4 1 2 是可解的 例如可取z i 1 o l 0 i m 4 7 4 8 4 9 4 1 0 垂n 垂1 2 易見這樣取定的咋b i d 母 1 滿足t l 時的 4 1 0 亦即有 等等 這樣 命 則有 由此可得 其中 t 1m 8 巧t 一 c z m o d 2 k oj i 2 磊 1 歹sm k o m a q z j 一6 i c 1 i n j l c c l c 2 c n 3 1 4 1 3 4 1 4 4 1 5 設l 砑是上述 b i 1s sn 1 歹 m 下 3 7 的解 而z 如定理3 2 5 的證 明中那樣 則有 由 4 1 5 與 4 1 6 可得 再由定理4 2 1 的證明可知有 加 c w w 叫 坩佃 i 暑 2 塒0 加 鋤 4 1 6 4 1 7 4 1 8 n 一 一 忍 七 2 q 小1 腳 玩 0 2k 一 即一 口 m 觸 i l l z 由 4 1 7 與 4 1 8 即得 i i x i i l 恬憶 由于耖是問題 4 2 的解 應該有 這樣 由 4 1 9 與 4 2 0 得出 l i 茹i i l i i 耖i i l 從而 茹為 4 2 3 的解 定理得證 1 x h l i y l i l 3 2 4 1 9 4 2 0 1 萬哲先 代數和編碼 科學出版社 1 9 8 0 參考文獻 2 丁石孫 王芬芳 高等代數 高等教育出版社 1 9 8 7 3 盧開澄 組合數學 清華大學出版社 1 9 8 3 4 華羅庚 數論導引 科學出版社 1 9 5 7 5 馮克勤 代數數論 科學出版社 2 0 0 0 1 6 孫淑玲 許胤龍 組合數學引論 中國科學技術大學出版社 1 9 9 9 7 馮貴良 吳新文 代數幾何碼 科學出版社 1 9 9 8 8 朱文余 孫琦 計算機密碼應用基礎 科學出版社 2 0 0 0 9 戴華 矩陣論 科學出版社 2 0 0 1 f 1 0 e l w y nr b e r l e k a m p a l g e b r a i cc o d i n gt h e o r y m c g r a w h i l lb o o kc o m p a n y 1 9 6 8 1 1 t h o m a sw h u n h e r f o r d a l g e b r a s p r i n g e r v e r l a g 1 9 7 4 1 1 2 b r u c es c l m e i e r a p p l i e dc r y p t o g r a p h y c h i n am a c h i n ep r e s s 2 0 0 0 1 3 b r u c es c h n e i e r s e c r e t sa n dl i e s d i g i t a ls e c u r i t yi nan e t w o r k e dw o r l d c h i n am a c h i n ep r e s s 2 0 0 1 1 4 f l b a u e rd e c r y p t e ds e c r e t s m e t h o d sa n dm a x i m so fc r y p t o l o g y s p r i n g e r v e r l a gb e r l i nh e i d e l b e r g 1 9 9 7 1 5 1g r a yj b r o n s o n p r o g r a m m i n gd e v e l o p m e n ta n dd e s i g nu s i n gc p o s ta n dt e l e c o m m u n i c a t i o n s p r e s s 2 0 0 2 1 6 w i l l i a mf o r d w i l l i a mt o p p s t r u c t u r e sw i t hc p r e n t i c eh a l l 1 9 9 6 f 1 7 c r r a o s k m i t r a g e n e r a l i z e di n v e r s eo fm a t r i c e sa n di t sa p p l i c a t i o n s j o h nw i l e ya n ds o n s 1 9 7 1 1 8 v n d l i a mf u l t o n a l g e