格雷码（Golay Code ）的
格雷码在通信中应用广泛。例如早在1980年俄罗斯航天仪表码研究所为了提高“星一地”、“地一星”链路数字指控信息的可靠性，研制和实现了格雷码的编码器和译码器，该设备在某型号飞行任务中成功地进行了试验。试验表明，使用格雷码，通信系统的误码率与未编码通信系统相比减少了1-3个数量级。
格雷码通常是指线性分组（23,12）码，最小距离d min =7，纠错能力 t=3。由
于223-12=2048=1+⎪⎪⎭⎫ ⎝⎛+⎪⎪⎭⎫ ⎝⎛+⎪⎪⎭⎫ ⎝⎛323223123 ，所以格雷码是完备码，其码重分布见下
面表1。
表1 格雷码的码重分布卷积编码
格雷码Golay (23，12)是循环码。对于汉明码、格雷码、二次剩余码、BCH 码和R-S 码等循环码的解码有很多方法，如梅杰特解码（Meggit, 1961）、大数逻辑解码（Reed ，1954）、门限解码（Massey, 1961）、信息组解码（Prange, 1962）。最经典的方法当属梅杰特解码，它充分利用了循环码的循环特征。 一、 格雷码的编码算法
输入：信源消息u （消息分组u ） 输出：码字v 1、处理： 信源输出为一系列二进制数字0和1。在分组码中，这些二进制信息序列分成
固定长度的消息分组（message blocks ）。每个消息分组记为u ，由k 个信息位组成。因此共有2k 种不同的消息。编码器按照一定的规则将输入的消息u 转换为二进制n 维向量v ，这里n >k 。此n 维向量v 就叫做消息u 的码字（codeword ）、码字矢量或码向量（code vector ）。 因此，对应于2k 种不同的消息，也有2k 种码字。这2k 个码字的集合就叫一个分组码（block code ）。若一个分组码可用，2k 个码字必须各不相同。因此，消息u 和码字v 存在一一对应关系。由于n 符号输出码字只取决于对应的k 比特输入消息，即每个消息是独立编码的，从而编码器是无记忆的，且可用组合逻辑电路来实现。 定义：一个长度为n ，有2k 个码字的分组码，当且仅当其2k 个码字构成域GF(2)
上所有n 维向量组成的向量空间的一个K 维子空间时被称为线性（linear ）(n, k)码。
格雷码Golay （n,k ）就是线性分组(n, k)码的一种。其编码算法即为使用生成
矩阵G ：
v = u ·G 。
例1-1 格雷码Golay (20,8,7) 的生成矩阵G 为： G = [ I k P ]k ×n
=⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦
⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡11
010111000110000000
0111110010010100000011101001010100100000011000111011000100001110011011000000100010110011011000000100100110011011000000100101101111000000000
1 ， v = u ·G ，
处理完毕。其他线性分组(n, k)码都可以照此办理即可。
线性分组(n, k)码的校正子（伴随式）有2n-k 个，设该码的纠错能力为t ，
那么重量小于或者等于t 的所有错误模式（图样）都要有唯一的校正子（伴随式）
与之对应，因而，对于二进制(n, k)码，有汉明限：2n-k
≣∑=⎪⎪⎭⎫ ⎝⎛t
i i n 0 ，当2n-k
=∑=⎪⎪⎭
⎫ ⎝⎛t
i i n 0
时，(n, k)码称为完备码（Perfect Code ）。完备码的校正子（伴随式）得到了充分的利用，不存在解码不唯一的问题，然而完备码不一定是纠错能力强的码，因为它的最小距离d min 未必最大。完备码也是稀少的，已知的二进制完备码有t=1的汉明码（Hamming Code ）和t=3的格雷码（Golay Code ），以及n 为奇数的简单重复(n,1)码。三进制完备码有t=2的（11,6,5）格雷码。
纠错能力t=1的完备码统称为汉明码。由定义可知，(n, k)汉明码应当满足下列条件：2n-k =1+n ，令校验位长m=n-k ，那么容易知道：
n=2m -1, k=2m -1-m, d min =3
汉明码的校验矩阵H 具有特殊的性质：它的m 维列向量正好是除零向量以外的所有可能的向量组合，共有2m -1个，恰好构成了H 矩阵的列数n 。
格雷码通常是指线性分组（23,12）码，最小距离d min =7，纠错能力 t=3。由
于223-12=2048=1+⎪⎪⎭⎫ ⎝⎛+⎪⎪⎭⎫ ⎝⎛+⎪⎪⎭⎫ ⎝⎛323223123 ，所以格雷码是完备码，其码重（码的重
量）分布见下面表0-1。
表1 格雷码的码重分布
备注：
1、格雷码Golay (20,8,7) 的生成矩阵G 为： G = [ I k P ]k ×n
=⎥
⎥⎥⎥⎥⎥⎥
⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣
⎡11
0101110001100000000111110010010100000011101001010100100000011000111011000100001110011011000000100010110011011000000100100110011011000000100101101111000000000
1 。
2、除了分组码之外，还有卷积码。卷积码编码器同样接受k比特分组的信息序列u，并产生n符号组的编码序列（码序列）v（卷积码编码中，符号u和v用来表示分组的序列而非单个分组）。但是，每一个编码分组不仅取决于当前单位时间对应的k比特消息组，而且与前m个消息组有关。此时，编码器的存储级数(memory order)为m。编码器所产生的所有可能的输出编码序列的集合构成了一个码。比值R=k/n称为码率（code rate）。由于编码器有存储单元，因而必须采用时序逻辑电路实现。
二、格雷码的译码算法
输入：接收向量r
输出：译码所得码字v*
1.处理（方案一：作为线性分组码）：
考虑一个（n，k）线性分组码，其生成矩阵为G，奇偶校验矩阵为H。令
v=( v0,v1, … ,v n-1)表示要通过有噪信道传输的码字，r = (r0,r1, … ,r n-1)为信道输出端接收到的码字。由于信道中的噪声，r可能与v不同。向量和e= r +v=( e0,e1,…,e n-1)是一个n维向量，其中r i≠v i时，e i=1，而r i= v i时，e i=0。该n维向量e称为差错向量(error vector)或错误模式或错误图样（error pattern）, 它直接指出接收向量r不同于传输码字v的位置。e中的1表示由于信道噪声引起的传输差错（transmission errors）。
接收向量r的译码包括如下三个步骤：
1、计算r的校正子（伴随式）s = r·H T；
2、确定校正子（伴随式）s = r·H T对应的陪集首e l，于是e l被假定为由信道
引起的错误模式（错误图样）；
3、将接收向量r译为码字v*=r+ e l。
上述译码方案被称为校正子（伴随式）译码（syndrome decoding）或查表译码（table lookup decoding）。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议