計算機問題求解代數(shù)編碼

計算機問題求解代數(shù)編碼04月19日問題1:為什么易于發(fā)現(xiàn)錯誤，甚至易于糾正錯誤的編碼方案非常重要？首先當(dāng)然是因為編碼無處不在，不僅如此…無處不在到什么程度？Wewillassumethattransmissionerrorsarerare,and,thatwhentheydooccur,theyoccurindependentlyineachbit.即使傳輸一個bit出錯概率不大…假如傳輸1個bit,出錯的概率是千分之五，假如要傳500個bits，那么：不出錯的概率是：8.2%;有一位錯的概率是：20.4%;有兩位錯的概率是；25.7%；而兩位以上錯誤的概率是：45.7%問題2：要發(fā)現(xiàn)收到的報文中的錯誤，最“straightforward”的方法是什么？問題2：要發(fā)現(xiàn)收到的報文中的錯誤，最“straightforward”的方法是什么？問題2’：要發(fā)現(xiàn)甚至糾正收到的報文中的錯誤，最“straightforward”的方法是什么？冗余無論是發(fā)現(xiàn)，甚至在某種假設(shè)下發(fā)現(xiàn)及糾正錯誤，總有的存在，必須的嗎？問題3：我們必須考慮物理信道會出錯，但又假設(shè)出錯“不多”，這是為什么？問題4.1：一個“編碼方案”究竟是什么？問題4.2：那么，一個好“編碼方案”究竟是好在哪里？兩個集合，兩個函數(shù)問題5：關(guān)于m,n的大小，你能說點什么？其實，這n和m之間大小的差別就是“冗余”Ifwearetodevelopefficienterror-detectinganderror-correctingcodes,wewillneedmoresophisticatedmathematicaltools.Acodeisan(n,m)-blockcodeiftheinformationthatistobecodedcanbedividedintoblocksofmbinarydigits,eachofwhichcanbeencodedintonbinarydigits.Morespecifically,an(n,m)-blockcodeconsistsofanencodingfunction兩個集合，兩個函數(shù)問題6：順便問一下：為什么這里說群論會給我們很大幫助？Grouptheorywillallowfastermethodsofencodinganddecodingmessages.問題7:在上面的假設(shè)下，采用最大相似度的解碼方法，你認為怎樣的codeword集合有利于發(fā)現(xiàn)并糾正錯碼？小提示：解碼過程可以理解為從receiveword定位到codeword，再從codeword解碼到明文組，其中最迷惑解碼人的是哪一步？問題8:你能從第7個問題的思考中，理解碼字hamming距離的本質(zhì)，以及隨后定義出來的編碼系統(tǒng)的最小距離的用意嗎？如果x=(1100),y=(1011),我們收到了一個碼1110,我們可以得到什么結(jié)論？最小碼距與糾錯能力的關(guān)系問題9：在設(shè)計編碼時怎么能比較方便地“控制”最小碼距呢？再看編碼函數(shù)：Z2mZ2n問題10.1：什么是好的碼字系統(tǒng)？問題10.2：我們是否應(yīng)該為我們的設(shè)想選擇一個數(shù)學(xué)工具來思考、保證？如何快速計算一個碼字系統(tǒng)的最小距離？但是，這樣算，仍然很慢！Theweight,w(x),ofabinarycodewordxisthenumberof1sinx.這是為什么?要求碼字“群”化的重要理由！這個編碼系統(tǒng)的查/糾錯能力是什么樣的？如何去構(gòu)造一個群編碼？1，(0,0,…,0)必定在子群中；2，任意一個碼字，它是自身的逆；3，確保所有的碼字在加法運算下是封閉的！其實很難，而且對最小距離的控制沒有“章法”我們需要科學(xué)的方法來構(gòu)造群編碼，甚至編碼函數(shù)Z2n群的子群矩陣計算幫我們找到群碼Fora5-tuplex=(x1;x2;x3;x4;x5)ttobeinthenullspaceofH,Hx=0.H3*5AcodeisalinearcodeifitisdeterminedbythenullspaceofsomematrixH∈Mm×n(Z2).Howaboutthe6-tuplex：

(010011)tisreceived?問題11:相對于我們要解決的問題，我們現(xiàn)在走了多遠？書上后面還有“一堆”定理，是用來解決什么問題的？11.1:是否任意的矩陣H,都有nullspace?11.2:在已知信息分組(m)前提下，什么樣的矩陣H,能得到最好的nullspace（線性碼）？以下以偶校驗編碼為例注意編碼函數(shù)型構(gòu)的轉(zhuǎn)變：

這種轉(zhuǎn)變意味著：用m位進行冗余以下聚焦在用n位碼字，編碼n-m位block信息，用m位冗余定理8.25理想的編碼函數(shù)：構(gòu)造一個n*(n-m)的01矩陣G，如果對于每個信息x，Gx能夠得到一個y，y是群碼字碼字群和矩陣G會有關(guān)聯(lián)嗎？

注意：G矩陣型構(gòu)nX(n-m)

x型構(gòu)(n-m)X1

Gx的型構(gòu)nX1編碼函數(shù)：Z2n-mZ2nE(x)=Gx(4,3)塊編碼為例：n=4,m=1,x的長度為3,1位冗余G:4*3矩陣；x:3*1矩陣兩種特殊的矩陣H是m

n矩陣;

G是n(n-m)矩陣Im單位矩陣用于何處？問題12:構(gòu)造出這樣的矩陣G,是為了什么?問題13:書上例23想說明什么?恰好是H的nullspace!這個方程組有何寓意？A矩陣是隨意的嗎？假設(shè)我們對m=3的block進行偶校驗，但只用1位進行冗余：I1=(1)A應(yīng)該如何設(shè)計？A=(1

1

1)H=(1

1

1

1)

線性碼的數(shù)學(xué)基礎(chǔ)這n-m位可以表達什么？這m位如何進行奇偶校驗的？取決于A矩陣和待編碼信息！你能“看出”101如何編碼為長度為6的碼字？101101線性碼的數(shù)學(xué)基礎(chǔ)問題14:現(xiàn)在我們離“目標(biāo)”還有多遠？給定待編碼塊大小n-m，冗余位大小m，是否任意的Hm*n都可以滿足查錯和糾錯需求？任意的H都可以唯一確定其nullspace，確定一個線性碼。這個線性碼的差錯和糾錯能力是取決于什么？考察以下塊大小為4，冗余3位的某個H：

He4(0001000)t=0，因此e4是H確定的線性碼字之一這個系統(tǒng)的最小查錯能力是多少？什么情況下，H的nullspace中會出現(xiàn)ei？線性碼的查錯能力證明的關(guān)鍵：ei是什么？Hei是什么？ei作為codeword，會帶來什么性質(zhì)？假如H的第k列全0，則Hek=0，所以ek是codeword,但w(ek)=1。

假如ei是codeword,則Hei=0，則H的第i列必然全是0。如果我們要實現(xiàn)1位糾錯能力，線性碼應(yīng)該具有什么特征？H應(yīng)該具有什么特征？

H(e4+e6)=0，因此e4+e6是H確定的線性碼字之一，該碼字權(quán)為2什么情況下，H的nullspace中不會出現(xiàn)兩個ei之和？考察以下塊大小為4，冗余3位的某個H：線性碼的糾錯能力證明的關(guān)鍵：注意：codeword中恰含兩個1就是該codeword恰好是ei+ej(i

j)注意：的充分必要條件顯然是：H的第i列和第j列完全一樣。你如何設(shè)計奇偶校驗矩陣使得能夠完成一位糾錯編碼？

比如m=4？有可能冗余2位完成任務(wù)嗎？3位？

終于到最后一步了……問題16：怎么解碼（糾碼）？如果只有一位錯，利用syndrome:Hx，可以判斷錯在哪里?；驹恚篢hesyndromeofareceivedworddepends

solelyontheerrorandnotonthetransmittedcodeword.如果不錯，e為0；如果一位錯：糾錯方案呼之欲出！基本原理：Thesyndromeofareceivedworddepen