北邮电信院杨鸿文老师通信课件上下册下册ln08

1、第 7 周Lecture Notes 8 2006/03/28线性分组码 问题Fig. 1是一个函数，它把 k 个信息比特组成的向量 u编为一个 n 比特向量 c。C 是所有可能编码结果的集合，它是线性向量空间0,1n 的一个子集。C 也就是函数f (u) 的值域。BSC 信道在中被模型化为发送的码字和错误图样 e 相加。向量 e 的元素也取于 GF(2)，e 中任何一个位置若为 1，表示这个位置发生了比特错误。译根据收到的向量 y 判断发送的码字是什么，译码结果是向量c ，译码结果可能正确（ c = c ），也可能不正确（ c ¹ c ）。译的输出究竟应该是码字，还是它所代表的信息

2、无关紧要，因为知道了码字就等于知道了信息，特别对于系统码，这个关系更为简明。ML 译码的译码函数可以写为c = argmin dH (y, c)(1)cÎC表示把收到的 y 译为 C 中离 y 最近的那个。Shannon 的理论说：对于给定的信道，有一个最大的传输能力（信道容量）。一定存在这样一种编码，使得 ML 译码后仍然有错的概率随着编码长度的增加而无限减小。的目标是：1寻求好的编码设计。它的传输能力尽量高（表现为编码率 k/n），抗差错能力尽量强(表现为能够纠正多少比特的错误)。2复杂度可以接受。复杂度表现为对量或者计算量的要求。按照Shannon的理论，如果编码足够长的话，随

3、机选择一种编码几乎就是一种好码。随机编码的意思是这样的：以(7,4)码为例，用掷硬币的方法决定出Table 1中*的内容。把这 16×7 个*号的内容都确定出来后，等于设计出了一种编码。注意这样的表格可以有216´7 种不同，Hamming码是其中之一（Table 2）。对于随机确定的这种编码，可以用查表法实现。具体电路如Fig. 2所示。ROM中存量为24 ´ 7bit 。对于任意(n, k ) 码，需要的量是2k ´ n 。随器加起来都不够储的就是Table 1，所需着k的增加，用。量将按指数速度增加。如果k达到数百，全世界所有的对于ML译码，如果直

4、接按照式(1)来做的话，需要计算2k 个Hamming距离，然后进行比较运算。其计算量是指数级的。ML译码也可以按函数查表来做。Table 3是译码函数表。按这样的方法实现译码需要的量是指数级的。因此，问题的焦点成为：寻找复杂度（计算量或量）可接受的编译码方法。要达到这一目的，就需要编码结构具备某种可操作的数学特性。1/5第 7 周Lecture Notes 8 2006/03/28Fig. 2 查表法实现编码Table 1 (7,4)随机选择编码Table 2 (7,4)码的编码函数Table 3 (7,4)Hamming 码的译码函数表2/5译码输入译码输出译码输入译码输出00000000

5、000001000001000001000001000001000001000001000000000000010000111000010100000110001111001011101001111000110000011100001100011110001110000110100010110000111001111101011111001111000111110011001001101100111010010001000100101110011011000001100100110000101010010100001011000100010011101000010101101011010101

6、0010101101011010101111010100101001010111101000110111011000101101010110001101000110110011000001111000100100001010011101010110100011010101100110110001011011101110110100011001001111100100110011011001编输入u3u2u1u0编输出(c6c5c4c3c2c1c0 )编输入u3u2u1u0编输出(c6c5c4c3c2c1c0 )000000000001000100001100010001111100110011

7、00001000101011010101011000110011010101110110000100010011011001100101010101010011101110101001100110011111011100000111011110011111111111编输入u3u2u1u0编输出(c6c5c4c3c2c1c0 )编输入u3u2u1u0编输出(c6c5c4c3c2c1c0 )0000*1000*0001*1001*0010*1010*0011*1011*0100*1100*0101*1101*0110*1110*0111*1111*第 7 周Lecture Notes 8 200

8、6/03/28二 线性分组码如果编码函数 f 是线性函数，则称这样的分组码为线性分组码。此时 f 是一种线性变换，因此可以写成c = uG(2)其中矩阵G叫生成矩阵。G必然是一个k×n的矩阵。若记g1 , g2 ,", gk 为G的第 1、2、k行，记u = (uk-1, uk-2 ,", u1, u0 ) ，则(2)可以写成æ g1 öç g ÷,", u , u2 ÷ = ug + u)çc = (ug +"+ u g, uk -1k -2ç÷k -1 1k -

9、2 2100 k#ç g ÷è k ø对于合理的编码，每一种信息输入应该对应有一个不同的编码结果，即编码结果必须有2k 种中包含全零码字(0, 0, 0,", 0) ；C不同，因此 G 的各行必须线性无关。另外容易看到：C中的元素对加法封闭；G 的每一行都在 C 中。实际上，Cg1, g2 ,", gk 是其一组基。了一个线性向量空间，任意给定 k 个线性不相关的向量，由其的线性空间就是一种线性分组码。对于给定的 C，其生成矩阵 G 不唯一，C 中的任意一组基都可以作为 G。 Hamming 码的生成矩阵为æ 1ç

10、 0010000100001011111011 ö0 ÷G = ç÷1 ÷(3)ç 0ç 01 ÷èø3/50100110010011101001000100010010111001101100000110110011001001101100101110010011001111100001110110111101011000101010010111001010101001010100001010110101101010000101110010001001110100101010011101010

11、110101111010001101110110001011110101001010010101011010100110011011001001100010110111011101101000110010011111001101100111110000111000111100101110100111100011000001010000011000011100000111100011110101111100111000011010001011000011100111110001111001111111111111011111011111011111011111011111011111011111

12、11111111第 7 周Lecture Notes 8 2006/03/28线性分组码的编运算是式(2)这样的矩阵运算。对于二进制编码，因为乘法只是和 0、1相乘，所以(2)中只有加法运算（逻辑异或），加法次数和G中 1 的个数有关，显然小于nk个。k 2若给定编码率为R，则运算次数小于，它是平方增长的，比指数级有大大的改善。R三 校验矩阵对于上述 Hamming码，编码结果是c = (c6c5c4c3c2c1c0 ) = (u3u2u1u0 p2 p1 p0 ) ，可以注意到编码结果满足线性方程组：ìc5 + c4 + c3 + c2 = 0ïc+ c + c + c

13、= 0í6531ïc+ c + c + c = 0î 6430写成矩阵形式为æ c6 öç c ÷ç5 ÷0 öç c4 ÷æ 0 öæ 0110101111100010 ÷ç c÷ = ç 0 ÷ç 1÷ç 3 ÷çç ÷ç 101 ÷ç cç 0 ÷÷è&

14、#248;çè ø2 ÷ç c1 ÷ç c ÷è 0 ø即HcT = 0(4)其中æ 00 ö110101111100010H = ç 10 ÷(5)ç÷ç 11 ÷èø字都满足线性方程组(4)的约束关叫监督矩阵或校验矩阵。这就是说，Hamming码的所系。由于H的秩为 3（任意 3 行或者 3 列线性无关），所以线性方程组(4)有 4 个变量是的，因而其解有 16 个。这 16 个解了码字空间C

15、。(4)这样的关系对任意的线性分组码都是存在的。以至于还可以把线性分组码定义为：如果集合C是形如(4)的某个线性方程组的解的集合，则称C为线性分组码。四 系统码一般来说，如果编输出的比特流中原样包含了信息比特，叫系统码。编码输出中的这些原始信息位也叫系统位。(n, k ) 码的前k个或者后k个是信息位。性分组码中，说一个码是系统码的意思一般是说：例如以(3)为生成矩阵的(7,4)码是系统码。但以下面这个生成矩阵产生的码是非系统的。æ 1ç 01 ö110000100001111101010 ÷G¢ = ç÷1 ÷(

16、6)ç 0ç 01 ÷èø比如：输入(1100)，编码结果是(1000011)，不是(1100*)的样子。系统码的生成矩阵一定包含幺阵 Ik 的所有列。(6)所给出的G¢ 中没有包含(0,1, 0, 0) 这个列。T4/5第 7 周Lecture Notes 8 2006/03/28五 码的等价性设有两个(n, k ) 编，一个输出的码集合是C1 ，另一个是C2 。称这两个编是等价的，如果下列之一满足：(1) C1 和C2 集合相同(2) C 2 只是C1 变换了比特顺序。每一个编码结果的许用码字都和一个信息码组对应，给定码的集合并不表示给定了信息码字和编码结果的关系。因此谈论码的等价性时不涉及信息比特的规则。上述条件(1)表示码字集合不变，条件(2)是说码字集合或许有变换，但这种变化只是改变了发送次序。比如原本的发送次序是 (c6c5c4c3c2c1c0 ) 自左至右顺序发送，改成了(c6c5c0c4c3c2c1 ) 这样的顺序。给定一个生成矩阵 G，如果对其进行初等行变换，则上述条件(1)始终满足。如果对 G的列调换次序，则条件(2)满足。因此，对 G 任意做初等行变换或者列交换后码还是等价的。同样的，给定一个监督矩阵 H，对 H 任意做初等行变换或者列交换后也是等价的。总能把一个非系统码的生成矩阵等价地