信息论武汉计算机学院八讲.pdf

第二部分纠错码

6、纠错编码的基本概念

7、线性分组码的基本理论

8、线性分组码在计算机系统中的应用

9、循环码的基本理论

10、典型循环码及应用

3

◼1957年Prange开始研究循环码；

◼循环码已成为线性分组码中最有理论意义和实用价值

的一种编码。

◼理论上，几乎所有的线性分组码皆可等效于一个循环

码。

◼实践上，由于码的循环特性而工程上容易实现。

◼数学上，可以借助近世代数作为工具进行深入研究。

4

◼举例1：面我们给出一个（7，4）线性分组码，

1011100

H=1110010

0111001

◼调整H中列的位置不改变码的距离特性，即所得到的

新码与原码等价。于是调整如下：

1110100

H’

0111010

1101011

◼因为信息位有4位，取值从0000-1111。根据，

C=MG，

可求出全部16个码字。

5

◼全体码字如下：

C1=1000110C8=1001011C15=0000000

C2=0100011C9=1100101

C3=1010001C10=1110010

C4=1101000C11=0111001

C5=0110100C12=1011100C16=1111111

C6=0011010C13=0101110

C7=0001101C14=0010111

◼奇妙特性：

①每个码字循环移位一位仍是一个码字。

②全体码字分布在几个圈中。

6

◼定义：

如果一个（n，k）线性分组码具有如下特性，则

称为循环码：设（c,c,…,c,c）是一个码字，则

01n-2n-1

其循环移位一位（c,c,c,…,c,）仍是一个码字。

n-101n-2

◼数学上，GF(2)上的一个（n，k）循环码是GF(2)上

的n维线性空间中的一个k维循环子空间。

7

◼循环码的多项式描述：

n

①一方面，GF(2)上的全体2个n维向量构成GF(2)上的n维线性空间V。