0


通信原理循环码基本原理

一、码多项式

一个长度为\large n的码组\large A=(a_{n-1},a_{n-2},...,a_0)可表示成如下多项式形式:

\large A(x)=a_{n-1} x^{n-1}+a_{n-2} x^{n-2}+\cdots+a_{1} x+a_{0}

多项式的系数就是码组中的各码元,\large x仅是码元位置标记 。

n=7 时:\large A(x)=a_{6} x^{6}+a_{5} x^{5}+a_{4} x^{4}+a_{3} x^{3}+a_{2} x^{2}+a_{1} x+a_{0}

例:码字(1100101)的多项式可表示为:

\large \begin{aligned} A(x) & =1 \cdot x^{6}+1 \cdot x^{5}+0 \cdot x^{4}+0 \cdot x^{3}+1 \cdot x^{2}+0 \cdot x+1 \\ & =x^{6}+x^{5}+x^{2}+1 \end{aligned}

二、码多项式的按模运算

一般来说,若一个整数\large m可以表示为

\large \frac{m}{n}=Q+\frac{p}{n}, \quad p<n\large Q为整数

则在模\large n运算下,有

\large m \equiv p\quad mod\quad n

即在模\large n运算下,一个整数\large m等于它被\large n除得到的余数。

对于任意多项式\large F(x)被一\large n次多项式\large N(x)除,得到商式\large Q(x)和一个小于\large n次的余式\large R(x),即

\large \frac{F(x)}{N(x)}=Q(x)+\frac{R(x)}{N(x)} \text { or } F(x)=N(x) Q(x)+R(x)

\large F(x)\equiv R(x) \quad mod \quad N(x)

三、循环码的码多项式

在循环码中,若\large A(x)是一个长为\large n的许用码组,则\large x^i\cdot A(x)在按模\large x^n+1运算下,也是该编码中的一个需用码组,即若

\large x^{i} \cdot A(x) \equiv A^{\prime}(x) (mod \left.\left(x^{n}+1\right)\right)

\large A^{\prime}(x)也是该编码中的一个需用码组,这是因为\large A^{\prime}(x)正是\large A(x)代表码组向左循环移位\large i次的结果。

四、循环码的生成矩阵

\large (n,k)循环码的\large 2^k个码组中挑出一个前面\large (k-1)位都是“0”的码组用\large g(x)表示:

根据循环性,\large g(x)\large xg(x)\large \large x^2g(x),...,\large x^{k-1}g(x)都是该循环码组的码组,且都线性无关。

因此,可以用这\large k个线性无关的码组可构成该循环码的生成矩阵\large G,即

\large G\left ( x \right ) =\left[\begin{array}{c} x^{k-1} g(x) \\ x^{k-2} g(x) \\ \vdots \\ x g(x) \\ g(x) \end{array}\right]

\large g(x)是循环码的核心。对于给定的\large k位信息码,由\large g(x)构造出\large G(x),从而产生\large (n,k)循环码。

\large g(x)称为循环码的生成多项式,一旦确定了\large g(x),则整个\large (n,k)循环码就被确定了。\large g(x)\large (n,k)循环码中唯一的常数项不为0的\large (n-k)次多项式。

例:

已知一种\large (7,3)循环码的全部码组为:

\large \begin{array}{llll} 0000000 & 0101110 & 1001011 & 1100101 \\ 0010111 & 0111001 & 1011100 & 1110010 \end{array}

试求:(1) 该循环码的生成多项式\large g(x)

       (2)生成矩阵![\large G(x)](https://latex.csdn.net/eq?%5Clarge%20G%28x%29)

码组是:0010111,码组中唯一一个4次多项式\large g(x)=x^{4}+x^{2}+x+1

\large G(x)=\begin{bmatrix} x^2g(x)\\ xg(x)\\ g(x) \end{bmatrix}= \left[\begin{array}{l} x^{6}+x^{4}+x^{3}+x^{2} \\ x^{5}+x^{3}+x^{2}+x \\ x^{4}+x^{2}+x+1 \end{array}\right] 或者 \large \boldsymbol{G}=\left[\begin{array}{c} \mathbf{1 0 1 1 1 0 0} \\ \mathbf{0 1 0 1 1 1 0} \\ \mathbf{0 0 1 0 1 1 1} \end{array}\right]

     ​​​ 

\large \begin{aligned} A(x)&=[a_6a_5a_4]G(x)=[a_6a_5a_4] \left[ \begin{array}{c} x^2g(x)\\ xg(x)\\ g(x) \end{array} \right]\\ & =a_{6} x^{2} g(x)+a_{5} x g(x)+a_{4} g(x) \\ & =\left(a_{6} x^{2}+a_{5} x+a_{4}\right) g(x) \end{aligned}

所有码多项式\large A(x)都可被\large g(x)整除,而且任意一个次数不大于\large (k-1)的多项式乘\large g(x)都是码多项式。

换言之,任一循环码多项式\large A(x)都是的倍式。

五、如何寻求任一\large (n,k)循环码循环码的生成多项式\large g(x)

\large \because任一循环码多项式\large A(x)都是\large g(x)的倍式。

\large \therefore\large g(x)本身也是一个码组,即有\large A^\prime(x)=g(x)

\large \because码组\large A^\prime(x)是一个\large (n-k)次多项式,故\large x^k\large A^\prime(x)是一个\large n次多项式。\large x^k\large A^\prime(x)在模\large x^n+1

运算下也是一个码组,故可以写作

\large \frac{x^{k} A^{\prime}(x)}{x^{n}+\mathbf{1}}=Q(x)+\frac{A(x)}{x^{n}+\mathbf{1}}

上式左端分子和分母都是n次多项式,故商式\large Q(x) = 1上式可化成

x^{k} A^{\prime}(x)=\left(x^{n}+\mathbf{1}\right)+A(x)

\large A^{\prime}(x)=g(x)\large A(x)=h(x)\cdot g(x)代入,化简后可以得到

\large x^{n}+1=g(x)\left[x^{k}-h(x)\right]

这表明:循环码的生成多项式**\large g(x)应该是\large (x^n+1)的一个\large (n-k)**次因子。

六、循环码的监督矩阵和监督多项式

1、监督多项式

由于生成多项式**\large g(x)能除尽\large (x^n+1)**,可以表示为

\large g(x)=g_{n-k} x^{n-k}+\cdots+g_{1} x+g_{0}

\large g_0=1,因此

\large x^{n}+1=g(x) h(x)

因为 ** **\large g(x)\large (x^n+1)的一个\large (n-k)次因子,则以\large g(x)*为生成多项式,则生成一个\large (n,k)循环码;而以\large h(x)为生成多项式,则生成一个\large (n,n-k)循环码,这两个循环码互为对偶码。*

由于上式是循环码必须满足的监督关系,因此许用码组\large h(x)称为监督多项式,不妨令

\large h(x)=h_{k} x^{k}+\cdots+h_{1} x+h_{0}

由监督关系可以知道

\large \begin{array}{l} g_{n-k} \cdot h_{k}=1 \\ g_{0} \cdot h_{0}=1 \\ g_{1} \cdot h_{0}+g_{0} \cdot h_{1}=0 \\ g_{2} \cdot h_{0}+g_{1} \cdot h_{1}+g_{0} \cdot h_{2}=0 \\ \cdots \\ g_{n-1} \cdot h_{0}+g_{n-2} \cdot h_{1}+\cdots+g_{n-k} \cdot h_{k-1}+\cdots+g_{0} \cdot h_{n-1}=0 \end{array}

因此可以由生成多项式确定监督多项式的系数。

2、监督矩阵

监督多项式\large h(x)=h_{k} x^{k}+\cdots+h_{1} x+h_{0},设\large h^{*}(x)\large h(x)逆多项式,则

\large h^{*}(x)=h_{0} x^{k}+h_{1} x^{k-1}+\cdots+h_{k-1} x+h_{k }

因为\large \boldsymbol{G} \boldsymbol{H}^{\mathrm{T}}=0, r=n-k。则监督矩阵\large \boldsymbol{H}_{r \times n}完全可由监督多项式\large h(x)的系数确定,由此可得循环码的监督矩阵为

\large \boldsymbol{H}_{r \times n}=\left[\begin{array}{c} x^{n-k-1} \cdot h^{*}(x) \\ x^{n-k-2} \cdot h^{*}(x) \\ \vdots \\ x \cdot h^{*}(x) \\ h^{*}(x) \end{array}\right]

\large =\left[\begin{array}{ccccccccccc} h_{0} & h_{1} & \cdots & h_{k-1} & h_{k} & 0 & 0 & \cdots & & & 0 \\ 0 & h_{0} & h_{1} & \cdots & h_{k-1} & h_{k} & 0 & 0 & \cdots & & 0 \\ 0 & 0 & h_{0} & h_{1} & \cdots & h_{k-1} & h_{k} & 0 & 0 & \cdots & 0 \\ \vdots & \vdots & & & & & & & & & \vdots \\ 0 & 0 & 0 & 0 & 0 & 0 & h_{0} & h_{1} & \cdots & h_{k-1} & h_{k} \end{array}\right]

上述的监督矩阵不是典型的,可将它经线性变化成典型形式,即典型的监督矩阵为

\large \boldsymbol{H}_{r \times n}=\left[\boldsymbol{P} \vdots \boldsymbol{I}_{r}\right]

标签: 算法 人工智能

本文转载自: https://blog.csdn.net/m0_51143578/article/details/128398749
版权归原作者 WHS-_-2022 所有, 如有侵权,请联系我们删除。

“通信原理循环码基本原理”的评论:

还没有评论