計(jì)算機(jī)問(wèn)題求解代數(shù)編碼

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

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

這種轉(zhuǎn)變意味著：用m位進(jìn)行冗余以下聚焦在用n位碼字，編碼n-m位block信息，用m位冗余定理8.25理想的編碼函數(shù)：構(gòu)造一個(gè)n*(n-m)的01矩陣G，如果對(duì)于每個(gè)信息x，Gx能夠得到一個(gè)y，y是群碼字碼字群和矩陣G會(huì)有關(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的長(zhǎng)度為3,1位冗余G:4*3矩陣；x:3*1矩陣兩種特殊的矩陣H是m

n矩陣;

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

1

1)H=(1

1

1

1)

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

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

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

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

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

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

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

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