信息论与编码：循环码.ppt

* 二．循环码编码器 1．基于生成多项式g（x）的编码器（n－k级编码器） 编码器电路的结构由生成多项式决定，生成多项式g（x）的最高次数为n-k，故编码器有n-k级移存器，故称n-k级编码器。 对于循环码的系统编码，首先要得到u(x) xn-k 除以g(x)的余式p(x)，再组合成系统码，即： 对于除法电路：一方面我们可以得到商，还可以得到余式。对于系统码编码我们可以先输出信息位，再输出余式（校验位）就可以得到系统码，另外由于被除式为u(x)x n-k，u(x)应从n-k级移存器的最前端输入。 * 编码过程： （1）门打开，k接“1”，消息数据u k-1 , ... u0移入电路，并同时送入信道，一旦k个消息全部移入电路，移存器中的n - k个数据就构成了余式的系数； （2）门关，断开反馈连接，k接“2”； （3）移出移存器中的数据 (校验元)，并送入信道，与k个信息位组成码字。 * 【例】（7，4）循环码， 若： * 编码过程：（k＝4） 节拍 输入 D0 D1 D2 输出 门开，k→1 0 1 0 0 0 1 1 1 1 0 1 2 0 1 0 1 1 3 1 1 0 0 0 4 － 1 0 0 1 门关，k→2 5 － 0 1 0 0 6 － 0 0 1 0 7 － 0 0 0 1 * 2．基于校验多项式h（x）的编码器（k级编码器） 编码器电路的结构由校验多项式决定，生成多项式h(x)的最高次数为k，故编码器有k级移存器，故称 k级编码器。 编码器电路 编码过程 （1）门1打开，门2关闭，k位消息数据u0，u1，... ，uk-1移入电路，并同时送入信道； （2）k位消息全部移入，门1关，门2开； （3）以后的每次移位产生一个校验元并送入信道，直到n－k个校验元全部产生并送入信道为止。然后门2关，门1开，准备下一组消息编码； * 【例】（7，4）循环码， k＝4级编码器 编码过程 输入 节拍 D0 D1 D2 D3 输出 门1开，门2关 1 0 0 0 0 0 1 1 1 0 0 0 1 0 2 0 1 0 0 0 1 3 1 0 1 0 1 － 4 1 1 0 1 1 门1关，门2开 － 5 0 1 1 0 0 － 6 0 0 1 1 0 － 7 0 0 0 1 0 * 3．两种编码器的比较 （1）基于g（x）的编码器为n－k级编码器，需要n－k级移存器； 基于h（x）的编码器为k级编码器，需要k级移存器。 （2）当n－k k时，采用n－k级编码器需要资源少； 当n－k k时，采用k级编码器需要资源少。 * § 8.4 循环码译码 一．译码步骤： 和线性分组码一样，循环码译码步骤分三步： （1）计算接收多项式r (x)的伴随多项式s (x)； （2）根据s (x)找出相应错误图样多项式e (x)； （3）将e (x)和r (x)模2加，得到译码输出v (x) 。 二．伴随式计算及错误检测 1．伴随式及计算 设接收多项式为r (x)，码多项式为v (x)，错误图样多项式为e (x)，则 用生成多项式g（x）除r（x），得 （求余运算） * 【定理】设g (x)是(n，k)系统循环码的生成多项式，接收字多项式为 r (x)，对应错误图样为e (x), 则 且它们的系数就是该接收字的伴随式。即 可见，循环码的伴随式计算电路就是一个接收多项式 r (x) 除以生成多项式g（x）的除法电路。 电路初始状态为0，当r (x)全部移入后，移存器中的内容为伴随式多项式s (x)。 * 2．伴随式计算电路的性质 由于码的循环结构，伴随式有个重要的性质，用定理描述。 【定理】设s (x)是r (x)的伴随式，则r (x)的循环移位 x · r (x)的伴随式s(1) (x)是s (x)在伴随式计算电路中无输入时右移一位的结果，即： 【推论】用生成多项式g (x)除x i s (x)所得余式s(i) (x)是r (x)经 i 次移位后r (i) (x)的伴随式。 说明：把含有s (x)的伴随式移存器的输入门断开，移位一次就得到r (1) (x)的伴随式s (1) (x) ，移位 i 次，就得到r (i) (x)的伴随式s (i) (x) 。 * 【例】（7，4）循环码， 计算 对应的伴随式。 伴随式计算电路 计算过程：（开始时，移存器清零） 节拍 输入 S0 S1 S2 节拍 输入 S0 S1 S2 1 0 0 0 0 6 0 1 1 1 2 1 1 0 0 7 0 1 0 1 s 3 1 1 1 0 8 — 1 0 0 s(1) 4 0 0 1 1 9 — 0 1 0 s(2) 5 1 0 1 1 * 由 计算电路性质的意义：对于在同一循环组中的接收字，