信息论与编码第六章3.ppt

信息论与编码-线性分组码 由S的定义式， ，即 共有n-k个方程，但有n个未知量，所以解不唯一。对于二进制，少一个方程导致两个解，少两个方程导致四个解，少k个方程导致有 个解，也就是说，可以解出 个不同的错误图样，从而对应了 个码字（码字的全部可能）。根据最大似然译码规则，应该译成可能性最大的那个码字。 信息论与编码-线性分组码 对于二进制对称信道，若差错概率为p，则错一个比特的概率（ ）大于错两个比特的概率（ ），…。所以，应该译成所有 个差错图样中重量最小的那一个。 但如果每接收一个R就要解一次方程组，显然太麻烦了。可以预先把不同S下的方程组解出来，并得到最大概率的那个错误图样，和错误图样对应的R，存成一个表格，译码的时候，只要根据不同的R查表，就可以得到对应的最大可能的码字。 信息论与编码-线性分组码 下表就是一个这样的表，叫做标准阵列译码表。表中有 列，每一列的头一个元素对应的是一个码字，所以共对应 个不同的码字；每一列的列首元素下，是 个禁用码字（即n维空间点中不是码字的那些点），代表该列首元素（码字）在不同差错图样下偏移后所对应的空间点，正好对应了 个不同的伴随式。全部的元素个数是 ，正好是n维矢量空间中总的点数，也就是说，每一个空间点 信息论与编码-线性分组码 都有其所对应的码字，这样，在译码的时候，当接收到一个R后，只要在标准阵列表中找到该R的位置，这一列的列首元素就是它应该译成的码字。 信息论与编码-线性分组码 标准阵列译码表 信息论与编码-线性分组码 表中第一行对应的是 个码字，相当于差错为零；第二行到第n+1行分别对应n个差错为1的差错图样；…。每一行的行首元素叫做陪集首，是该行所对应的错误图样。 但是，错误图样数有 个，标准阵列译码表只有 行，代表 个伴随式和错误图样。那么，怎么从 个错误图样中选择 个，作为陪集首？ 信息论与编码-线性分组码 原则当然是要使得译码的错误概率最小。前面已经说过，对BSC信道，当错误概率p0.5时，产生一个错误的概率比产生两个错误的概率要大，产生两个错误的概率比产生3个错误的概率要大，…。总之，错误图样重量越小，产生的可能性就越大。因此，译码器必须首先保证能正确纠正这些出现可能性比较大的错误图样，这相当于构造标准阵列译码表时，要求按照错误图样重量从轻到重的顺序挑选为陪首集。 信息论与编码-线性分组码 例题：某（5，2）系统线性码的生成矩阵是 设收到的码是R=(10101)，请先构造该码的标准阵列译码表，然后译出发码的估值C。 H=[PT┆I3]= = s1＝e1h11+e2h12+e3h13+e4h14+e5h15 = e1+e2+e3 s2 = e1h21+e2h22+e3h23+e4h24+e5h25= e1+e4 s3 = e1h31+e3h32+e3h33+e4h34+e5h35= e1+e2+e5 解： 对应（s1,s2,s3）=(111),e=(10000),(01010),(00111)和 (11101)四种错误图样 信息论与编码-线性分组码 信息论与编码-线性分组码 标准阵列译码表 n-k=3， ，即标准阵列译码表共有8行，每行代表一种错误图样。 按照错误图样重量从轻到重的顺序，无差错（错误图样重量为0）的有一种，重量为1的有 种，重量为2的有 种。 我们挑选的陪首集是1种无错误（重量为0），5种有一个错误（重量为1）和重量为2的10 种里面的2种。 信息论与编码-线性分组码 码字共有 种，将信息组的可能组合(00)、(01)、(10)、(11)代入生成矩阵，得到四个码字为：(00000)、(10111)、(01101)、(11010)。 得到的标准阵列译码表如下图所示： 信息论与编码-线性分组码 标准阵列译码表 S1=000 E1=00000 C2=10111 C3=01101 C4=11010 S2=111 E2=10000 00111 11101 01010 S3=101 E3=01000 11111 00101 10010 S4=100 E4=00100 10011 01001 11110 S5=010 E5=00010 10101 01111 11000 S6=001 E6=00001 10110 01100 11011 S7=011 E7=00011