基于系統(tǒng)碼信息位搜索的二元(24，12，8)Golay譯碼算法*

江寶安

（重慶郵電大學(xué) 移通學(xué)院，重慶 400065）

基于系統(tǒng)碼信息位搜索的二元(24，12，8)Golay譯碼算法*

江寶安

（重慶郵電大學(xué) 移通學(xué)院，重慶 400065）

針對（24，12，8）Golay譯碼問題，提出一種新的基于系統(tǒng)碼信息位搜索的譯碼算法。該算法定義新的校正子，由接收到的信息位計算監(jiān)督位，校正子由信息位計算出的監(jiān)督位和接收的監(jiān)督位相加共同確定，且具有可分性。譯碼只搜索信息位錯誤，不搜索監(jiān)督位錯誤，與在整個碼空間搜索錯誤位的一般線性分組碼譯碼算法相比，該算法大幅降低了計算量，特別對糾多個錯誤位的（24，12，8）Golay碼更加有效，同時也適用于循環(huán)碼、BCH碼和LDPC碼的譯碼。

糾錯碼；線性分組碼；校正子；譯碼算法；循環(huán)碼

0 引 言

二元（23，12，7）Golay碼是線性分組碼中的循環(huán)碼，最小距離為7，，表示下限取整，能夠糾正23位碼字中的任何3個或更少的隨機差錯的組合。

Golay循環(huán)碼在伽羅華域GF(2)的因式分解為：

生成多項式為：

由于滿足完備碼（Perfect Code）公式：

可見，二元（23，12，7）Golay碼是唯一的可糾3個錯誤的完備碼，具有良好的代數(shù)結(jié)構(gòu)，在深空探測及通信中具有重要的應(yīng)用價值。

（23，12，7）Golay碼可以通過對每個碼字增加一位總的奇偶校驗位來進(jìn)行擴展，生成（24，12，8）碼。（24，12，8）碼最小距離為8，能夠糾正所有含3個或更少差錯的錯誤模式，并能檢測所有含4個差錯的錯誤模式。由于（24，12，8）Golay碼碼長為24位，3個字節(jié)，在某些應(yīng)用方面更簡便，也更常用。

1 新的系統(tǒng)碼譯碼算法

一般的Cb(n,k,d)系統(tǒng)碼生成矩陣為G=[Ik×kPk×(n-k)]，其中Ik×k為k階單位陣，P(n-k)×k為監(jiān)督矩陣，簡寫為G=[I P]。因此，有：

其中m表示信息位。

由于存在信道噪聲，所以接收碼為：

其中em表示信息位錯誤，ep表示監(jiān)督位錯誤。

定義新的校正子S（Syndrome），見式（8），如圖1所示。

圖1 校正子S

故校正子S由信息位錯誤em和校驗位錯誤ep共同確定，且具有可分性。譯碼器的主要任務(wù)就是如何從S中基于最小錯誤準(zhǔn)則得到em，從而譯出：

由最小錯誤概率準(zhǔn)則，譯碼算法如下：

需說明的是，這里w(·)表示求Hamming權(quán)重。

2 二元擴展(24，12，8)Golay的譯碼算法

二元（24，12，8）Golay編碼所用的生成矩陣見式（10）：

二元（24，12，8）Golay相應(yīng)的監(jiān)督矩陣見式（11）。

任設(shè)二元（24，12，8）Golay碼，見式（12）。

假設(shè)接收碼為式（13），信息位有2個錯誤位，監(jiān)督位有1位錯誤。先用接收碼的前12位信息位乘監(jiān)督矩陣P，再加接收碼的后12位監(jiān)督位，得校正子S，由校正子S的Hamming權(quán)重確定信息位是否有錯，見式（14）。

滿足式（16）的hamming權(quán)值小于1：

所以，可以直接糾正信息位錯誤，而不用搜索和糾正監(jiān)督位錯誤。

假設(shè)接收碼為式（18），信息位有3個錯誤位，監(jiān)督位沒有錯誤：

滿足式（21）的hamming權(quán)值小于等于0：

所以，可以直接糾正信息位錯誤，而不用搜索和糾正監(jiān)督位錯誤。

類似地，其他的二元（24，12，8）Golay的誤碼形式只要在糾錯范圍內(nèi)，都可以以相同的算法糾正。

3 結(jié) 語

本算法利用系統(tǒng)碼的搜索信息位錯誤位，C(n,k,d)中糾正t信息位錯誤最多搜索次。對糾多個錯誤位的系統(tǒng)碼，信息位相對整個碼長更短。相對于一般在整個碼空間搜索錯誤位的算法，本算法只搜索信息位錯誤，不搜索﹑不糾正監(jiān)督位錯誤，極大地減少了計算量。同時，對能糾正3個錯誤位的二元（24，12，8）Golay碼而言，與一般的譯碼算法相比，它明顯減少了計算量。此外，由于能糾正多個錯誤位的循環(huán)碼﹑BCH碼和LDPC碼本質(zhì)上是線性分組碼，有相應(yīng)的等效系統(tǒng)碼，所以本文提出的算法也適用于這些碼的譯碼。

[1] Sweeney P.Error Control Coding.From Theory to Practice[M].New Jersey:W iley,2002:67-83.

[2] Jorge Casti?eira Moreira，Essentials of Error Control Coding[M].New Jersey:Wiley,2006:41-61.

(24,12,8)Golay Decoding Algorithm based on Searching Information Error of System Code

JIANG Bao-an

(University of Post and Telecommunication of ChongQing, Chongqing 400065, China)

A novel(24,12,8) Golay decoding algorithm based on searching information error of system code is proposed, which defines a new syndrome adding jointly by the received supervision bit and the supervision bits computing from the received information bits. The decoding algorithm only searches information-bit errors, no parity-bit errors. As compared with the general linear block-code decoding algorithm to search the entire code space error bits, this proposed decoding algorithm, could greatly reduce the amount of calculation, and is more effective for correcting multiple error bits of(24,12,8) Golay code, also applicable to decoding cyclic codes, BCH codes and LDPC codes.

Golay; linear block code; syndrome; decoding algorithm; cyclic code

TP393.03

A

1002-0802(2016)-11-1429-04

10.3969/j.issn.1002-0802.2016.11.003

江寶安（1974—），男，碩士，講師，主要研究方向為信號處理與通信理論。

2016-07-20；

2016-10-24 Received date:2016-07-20;Revised date:2016-10-24