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

江寶安

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

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

江寶安

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

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

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

0 引 言

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

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

生成多項(xiàng)式為：

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

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

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

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

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

其中m表示信息位。

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

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

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

圖1 校正子S

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié) 語(yǔ)

本算法利用系統(tǒng)碼的搜索信息位錯(cuò)誤位，C(n,k,d)中糾正t信息位錯(cuò)誤最多搜索次。對(duì)糾多個(gè)錯(cuò)誤位的系統(tǒng)碼，信息位相對(duì)整個(gè)碼長(zhǎng)更短。相對(duì)于一般在整個(gè)碼空間搜索錯(cuò)誤位的算法，本算法只搜索信息位錯(cuò)誤，不搜索﹑不糾正監(jiān)督位錯(cuò)誤，極大地減少了計(jì)算量。同時(shí)，對(duì)能糾正3個(gè)錯(cuò)誤位的二元（24，12，8）Golay碼而言，與一般的譯碼算法相比，它明顯減少了計(jì)算量。此外，由于能糾正多個(gè)錯(cuò)誤位的循環(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—），男，碩士，講師，主要研究方向?yàn)樾盘?hào)處理與通信理論。

2016-07-20；

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