區塊碼解碼方法與裝置的製作方法
2023-08-10 03:38:41
專利名稱：區塊碼解碼方法與裝置的製作方法
技術領域：
本發明有關於一種區塊碼解碼方法與裝置，尤指一種低複雜度的區塊碼解碼方法
與裝置。
背景技術：
在各種傳輸與通信系統中，往往需要正確地傳輸與接收大量的數據，尤其在長距 離的信道或無線通信系統中，可靠而無誤的接收數字資訊是很重要的課題。然而在傳送數 據或信息時，通常是經由某一傳送信道到達接收者，但往往會因為硬體設備的不良，外界的 幹擾，功率的消散，噪聲或多路徑衰減，或是電子設備的敏感而有錯誤產生，而導致數字數 據無法被正確的傳輸或可靠的接收，因此，可靠的數據傳輸往往是困難的。
針對提高信道數據傳輸的可靠性，目前已發展出許多的方法，例如，應用前向 錯誤校正(FEC)碼及其它裝置來定位、抵銷、校正及/或消除這些錯誤，根據特定編碼 (encoding)型式的編碼手冊，建立許多預定的碼字(codeword)，並用來將欲傳輸的數據編 碼，一旦編碼完成，在傳輸過程中被引入的錯誤，有機會在解碼(decoding)過程中，利用已 知的數學處理方法，將其定位並校正。 在信息傳輸的過程中，信息編碼器將原始信息轉換成一串二進位數字(位元， bit)的序列，稱為信息序列(information sequence)u。廣義的「編碼」包括邏輯到數字轉 換(A/D conversion, ADC)、消息源編碼(source coding)，禾口信道編碼(channel coding) 等等。其中，信道編碼是提升數字通信可靠度的一種技術，其通過對數位訊號進行除錯 控制(error control)，可以提升傳輸的質與量。信道編碼器將信息序列(information sequence)轉換成一個離散的編碼序列(encoded sequence) v，稱為碼字(codeword)。
—般碼字v仍為一串二進位數字序列，但某些應用場合也有用到非二進位者。任 何一個n位元的碼字(codeword)可視為n維空間中的一個向量，而此向量的每一坐標分量 為該碼字中的每個位元，例如，我們可將碼字101寫成一個一維的編碼向量1= (101)。任 二個碼字其向量中相異分量的個數被定義為漢明距離(Hamming distance) dH，例如編碼向 量Z(101)和x(110)的漢明距離dH(u)即2，因為第二和第三分量不同。對一個經設計的 編碼系統而言，其有效的碼字之間的最小漢明距離稱為最小漢明距離cLn，此即解碼時其容 許錯誤的位元個數，當一個碼字中的傳輸錯誤個數小於dmin時，即可偵測到錯誤的發生。
—般常用的解碼校正方式是通過相關(correlation)運算來取得所接收信息所 最相近的碼字作為決定碼(decision) ，二個向量的關聯運算可定義為其中對應分量的乘 積，例如，2L(Xp x2， x3. xn)與i(yi， y2， y3， .... yn)的關聯運算④可表示如下
2￡(xi,x2,x3...xn) y(yi，y2，y3，…yn戶x^yi+x^y2+x盧y3…x^yn 在二進位系統中，所接收到的信息與碼字進行關聯運算所得的值愈大，即代表所 接收到的信息愈接近該碼字，也就是該碼字愈接近可能的正確解。 如果傳輸的區塊碼本身有一些特性，例如線性(linear)或周期性(cyclic)，則可 以大大降低解碼的複雜度，然而當區塊碼本身沒有特別的特性可以降低解碼複雜度時，只
3好將收到的信息區塊和所有的碼字作相關(correlation)運算，找出相關性最高的碼字作 為決定碼。 當區塊碼的長度(length)愈來愈長、容量愈來愈大時，關聯運算的數量也急劇的 提高，進而影響信道傳輸的效能，為了降低關聯運算的數量，為了減低關聯運算的次數，對 於具有最小漢明距離的編碼系統，只需考慮與該接收信息最小漢明距離以內的碼字作關聯 運算，如此即所謂的限制距離解碼(bounded distance decoding)，然而隨著信息量的提 高，與更快更精確的傳輸要求，既有的解碼方法其效率仍有所不足之處，因此，在不影響信 道傳輸的可靠性下，尋找更簡單又有效率的解碼方法很迫切需要的，因此申請人構思出本 申請"區塊碼解碼方法與裝置"，以下為本申請的簡要說明。
發明內容
本發明的目的之一在於解決先前技術的問題。 本發明的另一目的在於提供一種運算量較少的區塊碼解碼方法與裝置。
根據本發明的實施例，提出一種區塊碼的解碼方法，其中第一信息碼經系統化編 碼(systematic encoding)後產生第一區塊碼，該第一區塊碼由該第信息碼與第一同位檢 查碼組成，該第一區塊碼經傳輸被接收為第一接收碼，該第一接收碼包括對應該第一信息 碼部分的第一接收信息碼，該方法包括(A)依照該第一接收信息碼的維度k與選定的距離 p，建立一組互斥或(exclusive-or，X0R)掩碼向量，其中該組X0R掩碼向量的維度為k且其 分量由二位元數值i或j所組成，該組X0R掩碼向量為有0 p個分量為i而其餘分量為j 的所有XOR掩碼向量的組合，代表該信息碼經傳輸後所有可能發生錯誤的型態，其中i代表 該信息碼傳輸錯誤的位元位置，j代表該信息碼傳輸無誤的位元位置；(B)將該第一接收信 息碼與該組X0R掩碼向量進行X0R運算，即該第一接收信息碼中對應X0R掩碼中數值i的 分量進行變位，該第一接收信息碼中對應XOR掩碼中數值j的分量保持不變，而得到一組第 二接收碼；(C)將該組第二接收碼再次進行系統化編碼，而產生一組第二區塊碼；以及(D) 將該第一接收碼與該組第二區塊碼進行關聯(correlation)運算，取該關聯運算所得值最 大的該組第二區塊碼其中之一為最可能解。 最可能解通過下列實施例及圖示說明，以便更深入了解本發明。
圖1為本發明的區塊碼的解碼方法的優選實施例的流程圖。
具體實施例方式
本發明將可由以下的實施例說明而得到充分了解，使得本領域的技術人員可以據 以完成，但是本發明實施例並非用來限制本發明的實施可能性。 在說明本發明實施例之前，首先對區塊碼再作進一步說明。對一個用於信道傳輸 的區塊碼而言，通常可以函數(n， k， t)來表示其特徵，其中n表示碼字的位元總長度，k代 表編碼前原始碼(信息碼)的位元長度，而t則是該區塊碼於傳輸並接收後可以被更正錯
誤的位元個數，其與最小漢明距離dmin的關係可表示為formula see original document page 4其中符號
表示最大整數函數(floorfunction)。另外，區塊碼可為系統化碼(systematic code)，其是指 被編碼後的區塊碼是由信息碼和檢查碼組成，例如在區塊碼v(x。， . . . xk—p zK， . . . zn—》中， (x。， . . . xk—》是信息碼而(zk， . . . zn—》則是檢查碼。請注意，於後述本發明實施例中該檢查 碼為同位檢查碼(parity check)，然而這並非對本發明的限制。 在現有技術中，當區塊碼經過信道傳輸後，接收端會收到一個對應該區塊碼的接
收信息i(y。， ... yH， yk， ... y『》，並將它和所有可能為該區塊碼的碼字作關聯運算找出最
大值argma—I>Wa其中{Ci,。 Ci,k—lCi,k 代表第i個碼字，如果碼字有q個位
元，則0《i < qk。因此，隨著碼字的位元個數越多，所需要作的關聯運算的次數也越多，即 qk次。現有技術(即限制距離解碼)為了減低關聯運算的次數，對於最小漢明距離為P的
編碼系統，只考慮與該接收信息i(y。， yH， yk，... y^)的漢明距離為p以內的碼字作關 聯運算，如此則所需作的關聯運算次數則可減少至(1+^" + (^+...+<^)次，其中，1次(即
c。"次)為考慮在該漢明距離p的條件下，信道傳輸過程中皆未產生錯誤的情況，cr為考慮在 該漢明距離p的條件下，信道傳輸過程中該區塊碼產生一個位元錯誤的情況，c;:則為考慮 在該漢明距離p的條件下，信道傳輸過程中該區塊碼產生p個位元錯誤的情況。 然而，與該接收信息工(y。， ...yk—n yk...yw)的漢明距離為p的碼字仍可能 相當多，也就是說當碼字的位元總長度n愈長及/或漢明距離p愈大，關聯運算次數
G+cr+c2"+…+ch就會愈多。有鑑於此，本發明提出一種方法與裝置來解決這一題，具
體地如以下的本案實施例所述。 本實施例針對當區塊碼最可能解為系統化碼的情形。請參考第一圖，其為本實施 例的流程圖。本實施例的傳送端(未顯示)所傳送的第一區塊碼^0^，...&-1，&，...、-1) =y(M，工)為系統化碼，其中第一信息碼M(x。， ...Xh)為欲傳送的信息碼，經編碼加入的 z(Zk，. . . zn—》則為同位檢查碼，經過信道傳送後接收端接收到信息(步驟101)，其為第一接
收碼n(y。， y" ， yk—" yk， yn—》=l (y。， ， yk—》+n2 (yk， yk+1， ， yn—》，其中l (y0， yi，... ， yk-》為第一接收信息碼，其為對應原信息碼的部分。 由於v為系統化編碼，因此，我們只需考慮擷取其中信息碼部分(k維)的漢明距 離為p餓情形(步驟102)。對於k維的信息碼，考慮其在漢明距離為p的範圍內所有可能
出現傳輸狀態，包括皆未出錯的情形及可能的錯誤狀態，建立一組互斥或掩碼(XOR mask)
M，該組互斥或掩碼由代表分別錯0 p個位元的傳輸模式集合(M。、MpM2.....Mp}，在每一
個互斥或掩碼也可表示成一個k維向量，其中以數字「0」代表對應的位元為正確的傳輸，數 字「1」代表其對應的位元預期將為錯誤。 因此，當考慮錯0個位元時僅有一個XOR掩碼為M。K0，0，0，0， . . . . ， 0) kxl}，其所 有的分量皆為O ;當考慮錯I個位元時則為MJ(O，O，O，O， .... ，l)kxl， (O，O，O，O， .... ，l，O)
kxl， (O，O，O，O， . . . l，0，0)kxl，......(l，O，O，， . .0，0，0)kxl}共Cf二k個XOR掩碼；當考慮錯
2個位元時則為M2{(0，0，0， ， l，l)kxl， (O，O，O， ... ，l，0，l)kxl， (O，O，O， ... l，O，O，l)
個XOR掩碼，同理，當考慮錯p個位元時則共有C-個XOR掩碼，該所有的XOR掩碼即代表智
， (O，O，O， . 0， 1， l，0)kxl， (O，O， ， l，O， l，O)0 p個位元時所有可能的傳輸結果。 其後，將第一接收信息碼& (y。， yi，... ， yk—》和所有的k維的XOR掩碼進行X0R運 算(步驟103) ， XOR運算的運算方式是變位而不進位，即第一接收信息碼in的分量對應於 該k維XOR掩碼的分量中為「1」的部分表示估計信道傳輸過程中將產生錯誤的分量，則對 該分量進行變位，「0」變位為「1」或「1」變位為「0」，而所接收到的第一接收信息碼rl的分 量對應於該k維XOR掩碼的分量中為「0」的部分表示估計信道傳輸過程中並未產生錯誤的 分量，故不改變其值。將第一接收信息碼￡1和所有的k維XOR掩碼進行XOR運算後，得到 相同於XOR掩碼數量(HCf +《+…+《)的字碼^ (x。' ，x/ ，...Xk—/ )，以下稱作第
二信息碼，該所有的第二信息碼H/即為基於該第一接收信息碼與該漢明距離P條件下所 有可能的信息碼的解。 將所有的第二信息碼n'(x。' ，Xl' ，...Xk-/ )再次進行編碼(步驟104)後，可得 到一組比對碼，即第二區塊碼I'(x。' ，x/ ，...Xh' ，z。' ，Zl' ，...zk—/ )(步驟105)，該 第二區塊碼I'即為所有可能的解，共有1+ C， + +.,.+ C-組，將該i + cf+ c2A + ,,. + c^
組第二區塊碼i'分別和該第一接收碼￡(y。， yi， ... ， y^， yk， ... yn-》作關聯運算(步驟 108)，取其最大值發生時的第二區塊碼x'即為該第一接收碼n的最可能解(109)。
在上述的過程中，由於僅針對系統化碼(n維)的信息碼部分建立k維(k <n)的XOR掩碼，且僅作i +《+ (^+，,， +《次的關聯運算，相較於先前技術中需作
i+Cr + C2"+…+(^次的關聯運算，因此顯然更進一步減少了所有需要的運算量。 如果我們在解碼過程中假設第一接收信息碼{y。. . . yK—卩的錯誤個數p不大於 k(O《p《k)，這樣的話當p愈小，所需執行的關聯運算次數愈少，以一個(16， 8， 2)特徵的 系統化二進位碼來說，如果全部做關聯運算需要作28次，即256次的關聯運算。當取編碼 系統的漢明距離為2時，即只考慮錯兩個位元時只要作37 ( 1 + <^8 +《)次的關聯運算，取
漢明距離為3時則是作93 ( 1+ + C28 +《)次的關聯運算，取漢明距離為4時則是作
163 ( 1 + Cf + C2s + C38 + C4s )次的關聯運算。 以最小漢明距離為2時的(16，8，2)特徵的系統化二進位碼為例。其中，第一信息 碼ll(x。， Xl， ...x7)為、欲傳送經過信道的信息，其經過系統化編碼後成為第一區塊碼x(U，
工)二X(X。，Xi ，..^7"。"1，...27)，其中經編碼加入的1(2。"1，...27)為同位檢查碼，經過
信道傳送後，所接收到的接收碼為第一接收碼i:(y。，yp... y15)。其後，先對第一接收碼i:(y。， y" y15) = [l， n2]中對應原信息碼的部分l (y。， y" y7)(稱作第一接收信息碼)和
預先建立的37個互斥或掩碼(X0Rmasks)Mj作互斥或(exclusive-or)運算。這37個掩碼 代表分別錯0 2個位元的錯誤模式集合{M 、 M2}，其中以數字「0」代表正確，數字「1」 代表錯誤 當錯0個位元時，M。為邁。,i(0，0，0，0，0，0，0，0); 當錯1個位元時，M丄為邁u(0，0，0，0，0，0，0，l)，nh,2(0，0，0，0，0，0，1，0)，
2h,3(0，0，0，0，0， l，O，O) ，2h,4(0，0，0，0， l，O，O，O) ， nh,5(0，0，0， l，O，O，O，O)，
邁l6(0，0， l，O，O，O，O，O)，邁l7(0， l，O，O，O，O，O，O)，邁u(1，0，0，0，0，0，0，0)共8個；
同理，錯2個位元時，M2為邁u(0，0，0，0，0，0， 1， 1)，邁2,2 (0， 0， 0， 0， 0， l，O， 1)，
邁2,3(0，0，0，0， l，O，O， 1)，邁2,4(0，0，0， l，O，O，O， 1)，亂5(0，0， l，O，O，O，O， 1)， 邁2,6(0， l，O，O，O，O，O， 1)，邁2,7(1，0，0，0，0，0，Q， 1)，亂8(0，0，0，0，0， 1， l，O)，
邁2,E 邁2,1 邁2,1 邁2,1 邁2,2 邁2,2 邁2,2
(O，O，O，O， l，O， l，O)，邁2,10(0，0，0， l，O，O， l，O)，邁2,n(0，0， l，O，O，O， l，O)， ;(O， l，O，O，O，O， l，O)，亂13(1，0，0，0，0，0， l，O)，亂14(0，0，0，0， 1， l，O，O)， ;(O，O，O， l，O， l，O，O)，亂16 (O，O， l，O，O， l，O，O)，亂17(0， l，O，O，O， l，O，O)， ;(l，O，O，O，O， l，O，O)，亂19(O，O，O， 1， l，O，O，O)，亂20(O，O， l，O， l，O，O，O)， ,(O， l，O，O， l，O，O，O)，亂22(1，0，0，0， l，O，O，O)，亂23(0，0， 1， l，O，O，O，O)， !(O， l，O， l，O，O，O，O)，亂5(1，0，0， l，O，O，O，O)，邁2,26(0， 1， l，O，O，O，O，O)， ,(l，O， l，O，O，O，O，O) ， &,28(1， l，O，O，O，O，O，O)，共有28個錯誤模式。 其中，互斥或(XOR)運算的運算方式是變位而不進位，例如，如果接收到的第一接
收碼n(y。， y"….yj = (o，o， i， i，o，o， i， i，o，o， i， i，o，o， i， i)，其對應原信息碼部分的第 一接收信息碼^(y。， y!， y7) = (o，o， i， i，o，o， i， i)，如果選擇與錯2個位元時的錯誤模
式亂2(0，0，0，0，0，1，0，1)進行互斥或運算(X0R)時，L餓分量對應於亂2的分量中為「1」 的部分表示估計信道傳輸過程中產生錯誤的分量，則對該分量進行變位，「0」變位為「1」或 「1」變位為「0」，而i^的分量対應於ffi^的分量中為「0」的部分表示估計信道傳輸過程中並 未產生錯誤的分量，不改變其值，因此，如果第一接收信息碼為(O，O，l，l，O，O，l，l)時，和 邁2,2(0，0，0，0，0，1，0，1)進行互斥或運算即為 (O，O， 1， l，O，O， 1， l)XOR(O，O，O，O，O， l，O， 1) = (0，0， 1， 1，0， 1， 1，0) 將互斥或運算的結果(第二信息碼)作為信息碼i' (x。' ，x/ ，...x7')再次進 行編碼後，可得到第二區塊碼X' (x。' ，Xl，...x7' ，z。' ，z/ ，...z7')，該第二區塊碼共 37組即為所有可能的正確碼，將該37組第二區塊碼分別和第一接收碼n(y。， yi， . . . y15)作 關聯運算，取最大值發生的第二區塊碼即為該第一接收碼i:(y。， yi，... y15)的最可能解了。
然而，如果以一般慣用的限制距離解碼(bounded distance decoding)來說，所接 收到的第一接收碼H(y。， yi， .. y15)必需分別和第一區塊碼v(u， = v(x。， Xl， .. x7， z。， Zl， ... z7)中所有可能出現0 2個的錯誤位元的情況作關聯運算，以找出最接近解，因此 必需作總共"6+《6+^6=1+16+12=137次的關聯運算，而經由本實施例所列舉的方
法僅需作37次的關聯運算，因此本實施例所達成的效益是顯著而明確的。 綜上所述，本發明通過根據最小漢明距離所預先決定的一組互斥或(X0R)掩碼，
可有效的簡化解碼時判斷所有可能解的程序與演算量，同時對於系統化碼，配合X0R掩碼
的使用，通過巧妙的安排僅需處理信息碼的最小漢明距離求解，大幅減少關聯運算的次數
與運算量，而得提升信道傳輸的效能，實屬難能的創新設計，深具產業價值，依法提出申請。 本領域的技術人員可以進行任何修飾，但是都不脫離由權利要求限定的本發明的範圍。
權利要求
一種解碼方法，用來解碼接收碼，該接收碼包含信息碼與檢查碼，該解碼方法包含依據位元錯誤個數與該信息碼的長度產生x個比對接收碼，其中任意二該比對接收碼均不相同；將該接收碼與每個該比對接收碼作關聯運算，以便產生x個運算結果；以及依據該x個運算結果，決定該x個比對接收碼的其中之一為該接收碼的最可能解；其中產生該x個比對接收碼與該檢查碼的長度無關，且該位元錯誤個數不大於該信息碼的長度。
2. 如權利要求1所述的解碼方法，其中該接收碼為系統化碼，且該檢查碼為同位檢查碼。
3. 如權利要求1所述的解碼方法，其中該位元錯誤個數為p，該信息碼的長度為k，該x等於nxr+…+q:。
4. 如權利要求1所述的解碼方法，其中該x個運算結果中的最大值所對應的該比對接 收碼為該接收碼的最可能解。
5. 如權利要求1所述的解碼方法，其中產生該x個比對接收碼的步驟包含 依據該位元錯誤個數與該信息碼的長度產生x個比對信息碼；以及 依據該x個比對信息碼產生該x個比對接收碼。
6. 如權利要求5所述的解碼方法，其中產生該x個比對信息碼的步驟包含 依據該位元錯誤個數與該信息碼的長度產生x個運算掩碼；以及利用該x個運算掩碼產生該x個比對信息碼； 其中每個該運算掩碼均不相同。
7. 如權利要求6所述的解碼方法，其中該x個運算掩碼為X0R掩碼。
8. 如權利要求5所述的解碼方法，其中依據該x個比對信息碼產生該x個比對接收碼 的步驟包含將該x個比對信息碼加以編碼，以便產生該x個比對接收碼。
9. 如權利要求1所述的解碼方法，其中產生該x個比對接收碼的步驟包含 依據該位元錯誤個數與該信息碼的長度產生x個運算掩碼；以及利用該x個運算掩碼產生該x個比對接收碼； 其中每個該運算掩碼均不相同。
10. 如權利要求9所述的解碼方法，其中該x個運算掩碼為X0R掩碼。
11. 如權利要求1所述的解碼方法，其中該位元錯誤個數小於該信息碼的長度。
全文摘要
本發明提供一種區塊碼解碼的方法與裝置，通過建立一組互斥或掩碼(XOR)組，可以大幅簡化限制距離解碼的程序並減少關聯運算的次數。該解碼方法包括拾取原始接收信息的信息碼部分，將該信息碼部分進行XOR掩碼運算後進行編碼可得一組比對碼，將該組比對碼分別與該原始接收信息進行關聯運算，取其最大值發生時對應的比對碼即為最可能解。
文檔編號H03M13/19GK101777919SQ200910002399
公開日2010年7月14日 申請日期2009年1月12日 優先權日2009年1月12日
發明者卓俊銘, 洪佳君, 王承康 申請人:瑞昱半導體股份有限公司