循环码生成矩阵与监督 (校验) 矩阵

这篇具有很好参考价值的文章主要介绍了循环码生成矩阵与监督 (校验) 矩阵。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

本专栏包含信息论与编码的核心知识,按知识点组织,可作为教学或学习的参考。markdown版本已归档至【Github仓库:https://github.com/timerring/information-theory 】或者公众号【AIShareLab】回复 信息论 获取。

循环码生成多项式与生成矩阵

定义:记 C ( x ) \mathrm{C}(x) C(x) 为 (n, k) 循环码的所有码字对应的多项式的集合, 若 g(x) 是 C ( x ) \mathrm{C}(x) C(x) 中除 0 多项式以外次数最低的多项式, 则称 g(x) 为这个循环码的生成多项式

定理1: ( n , k ) (\boldsymbol{n}, \boldsymbol{k}) (n,k) 循环码中, 必定存在一个次数最小的唯一的码多项式g(x) , 称为生成多项式,
g ( x ) = x r + g r − 1 x r − 1 + ⋯ + g 1 x + 1 g(x)=x^{r}+g_{r-1} x^{r-1}+\cdots+g_{1} x+1 g(x)=xr+gr1xr1++g1x+1
其中: r = n − k r=n-k r=nk .

该码集中任意码字的码多项式必为g(x)的倍式。

非系统循环码的编码:
c ( x ) = u ( x ) g ( x ) c(x)=u(x) g(x) c(x)=u(x)g(x)

设某 (7,4) 循环码的生成多项式为 g ( x ) = x 3 + x + 1 g(x)=x^{3}+x+1 g(x)=x3+x+1,问信息串 0110 的循环码是什么?

解:

c ( x ) = u ( x ) g ( x ) = ( x 2 + x ) ( x 3 + x + 1 ) = x 5 + x 4 + x 3 + x c(x)=u(x) g(x)=(x^{2}+x)(x^{3}+x+1)=x^{5}+x^{4}+x^{3}+x c(x)=u(x)g(x)=(x2+x)(x3+x+1)=x5+x4+x3+x

故码字为: 0111010

定理2: 当且仅当 g(x) 是 x n + 1 x^{n+1} xn+1 r = n − k r=n-k r=nk 次因式时, g(x)是(n, k)循环码的生成多项式。

定理3: (n, k) 循环码的校验多项式为
h ( x ) = x n + 1 g ( x ) = h k x k + h k − 1 x k − 1 + ⋯ + h 1 x + h 0 \begin{array}{l} h(x)=\frac{x^{n}+1}{g(x)} \\ =h_{k} x^{k}+h_{k-1} x^{k-1}+\cdots+h_{1} x+h_{0} \end{array} h(x)=g(x)xn+1=hkxk+hk1xk1++h1x+h0
写出下面(7,3)循环码的生成多项式

循环码生成多项式求生成矩阵,Information Theory,矩阵,线性代数,信息论
g ( x ) = x 4 + x 3 + x 2 + 1 a r r o w 0011101 g(x)=x^{4}+x^{3}+x^{2}+1 arrow 0011101 g(x)=x4+x3+x2+1arrow0011101
(1) 生成多项式、生成矩阵

循环码生成多项式的特点:

  • g(x) 的 0 次项是 1 ;
  • g(x) 唯一确定, 即它是码多项式中除 0 多项式以外次数最低的多项式;
  • 循环码每一码多项式都是 g(x) 的倍式, 且每一个小于等于 (n-1) 次的 g(x) 倍式一定是码多项式;
  • g(x) 的次数为 (n-k) ;
  • g(x) 是 x n + 1 x^{n}+1 xn+1 的一个因子。

为了保证构成的生成矩阵 G 的各行线性不相关, 通常用生成多项式 g(x) 来构造生成矩阵; 若码多项式为降幂排列,
g ( x ) = g n − k x n − k + g n − k − 1 x n − k − 1 + ⋯ + g 1 x + g 0 , r = n − k C ( x ) = u G ( x ) = ( u k − 1 u k − 2 ⋯ u 0 ) G ( x ) = u k − 1 x k − 1 g ( x ) + u k − 2 x k − 2 g ( x ) + ⋯ + u 0 g ( x ) G ( x ) = [ x k − 1 g ( x ) x k − 2 g ( x ) ⋮ g ( x ) ] r i g h t a r r o w G = [ g r g r − 1 ⋯ g 1 g 0 0 0 ⋯ 0 0 g r g r − 1 ⋯ g 1 g 0 0 ⋯ 0 ⋮ ⋮ 0 ⋯ 0 0 g r g r − 1 ⋯ g 1 g 0 ] \begin{array}{l} g(x)=g_{n-k} x^{n-k}+g_{n-k-1} x^{n-k-1}+\cdots+g_{1} x+g_{0}, r=n-k \\ C(x)=\mathbf{u G}(x)=(u_{k-1} u_{k-2} \cdots u_{0}) \mathbf{G}(x) \\ =u_{k-1} x^{k-1} g(x)+u_{k-2} x^{k-2} g(x)+\cdots+u_{0} g(x) \\ G(x)=[\begin{array}{c} x^{k-1} g(x) \\ x^{k-2} g(x) \\ \vdots \\ g(x) \end{array}] rightarrow G=[\begin{array}{ccccccccc} g_{r} & g_{r-1} & \cdots & g_{1} & g_{0} & 0 & 0 & \cdots & 0 \\ 0 & g_{r} & g_{r-1} & \cdots & g_{1} & g_{0} & 0 & \cdots & 0 \\ & \vdots & & & & & \vdots & & \\ 0 & \cdots & 0 & 0 & g_{r} & g_{r-1} & \cdots & g_{1} & g_{0} \end{array}] \\ \end{array} g(x)=gnkxnk+gnk1xnk1++g1x+g0,r=nkC(x)=uG(x)=(uk1uk2u0)G(x)=uk1xk1g(x)+uk2xk2g(x)++u0g(x)G(x)=[xk1g(x)xk2g(x)g(x)]rightarrowG=[gr00gr1grgr10g10g0g1gr0g0gr100g100g0]
显然, 上式不符合 G = ( I k : Q ) \mathbf{G}=(\mathbf{I}_{k}: \mathbf{Q}) G=(Ik:Q) 形式, 所以此生成矩阵不是典型形式。

系统码生成矩阵的构造

系统码-信息位在码字高位, 因此编码时需要先将信息位置于码字高位, 即 u(x) \bullet x^{n-k} 。 码字低位为校验位,如何获得?
c ( x )   m o d   g ( x ) = 0 c ( x ) = u ( x ) ⋅ x n − k + r ( x ) 0 = { [ u ( x ) x n − k ]   m o d   g ( x ) + r ( x ) } = r ( x ) [ u ( x ) x n − k ]   m o d   g ( x ) \begin{array}{c} c(x)_{\bmod g(x)}=0 \\ c(x)=u(x) \cdot x^{n-k}+r(x) \\ \mathbf{0}=\{[u(x) x^{n-k}]_{\bmod g(x)}+r(x)\} \end{array} \quad \stackrel{r(x)}{=}[u(x) x^{n-k}] \bmod g(x) c(x)modg(x)=0c(x)=u(x)xnk+r(x)0={[u(x)xnk]modg(x)+r(x)}=r(x)[u(x)xnk]modg(x)
(2) 系统循环码

系统循环码的编码:

a. 选择一信息码多项式 μ ( x ) \mu(x) μ(x) , 使 r ( x ) = x n − k μ ( x )   m o d   g ( x ) \quad r(x)=x^{n-k} \mu(x) \bmod g(x) r(x)=xnkμ(x)modg(x)

b. 产生系统循环码式 c ( x ) = x n − k μ ( x ) + r ( x ) \mathrm{c}(x)=x^{n-k} \mu(x)+r(x) c(x)=xnkμ(x)+r(x)

有一 (15, 11) 汉明循环码, 其生成多项式 g ( x ) = x 4 + x + 1 g(x)=x^{4}+x+1 g(x)=x4+x+1 , 若输入信息分组为 (10010010010), 求出 (15,11) 系统循环码字。

解: u ( x ) = x 10 + x 7 + x 4 + x u(x)=x^{10}+x^{7}+x^{4}+x u(x)=x10+x7+x4+x
x n − k u ( x ) = x 4 u ( x ) = x 14 + x 11 + x 8 + x 5 r ( x ) = [ x 4 u ( x ) ]   m o d   g ( x ) = x 2 ∴ c ( x ) = x 14 + x 11 + x 8 + x 5 + x 2 c = 10010010010 ( 0100 ) 监督位 \begin{array}{l} x^{n-k} u(x)=x^{4} u(x)=x^{14}+x^{11}+x^{8}+x^{5} \\ r(x)=[x^{4} u(x)] \bmod g(x)=x^{2} \\ \therefore c(x)=x^{14}+x^{11}+x^{8}+x^{5}+x^{2} \\ c=10010010010(0100)监督位 \end{array} xnku(x)=x4u(x)=x14+x11+x8+x5r(x)=[x4u(x)]modg(x)=x2c(x)=x14+x11+x8+x5+x2c=10010010010(0100)监督位
非系统码: c ( x ) = u ( x ) g ( x ) = x 14 + x 10 + x 7 + x 4 + x 2 + x c(x)=u(x) g(x)=x^{14}+x^{10}+x^{7}+x^{4}+x^{2}+x c(x)=u(x)g(x)=x14+x10+x7+x4+x2+x c=1000100100101100

已知某循环码生成多项式为 g ( x ) = x 8 + x 6 + x 4 + x 2 + 1 g(x)=x^{8}+x^{6}+x^{4}+x^{2}+1 g(x)=x8+x6+x4+x2+1,那么采用此多项式生成循环码时,校验位有 [8] 位。

已知某循环码生成多项式为 g ( x ) = x 8 + x 6 + x 4 + x 2 + 1 g(x)=x^{8}+x^{6}+x^{4}+x^{2}+1 g(x)=x8+x6+x4+x2+1,证明该多项式是 x 10 + 1 x^{10}+1 x10+1的一个因式。 直接长除即可,这里不多赘述。

请写出生成多项式为 g ( x ) = x 8 + x 6 + x 4 + x 2 + 1 g(x)=x^{8}+x^{6}+x^{4}+x^{2}+1 g(x)=x8+x6+x4+x2+1的系统型循环码 (10 ,2) 的码表。并说明该码至少能纠几位错。

循环码生成多项式求生成矩阵,Information Theory,矩阵,线性代数,信息论

d min ⁡ d_{\min } dmin=5, 能纠2位错

系统码的循环码生成矩阵

G ( x ) = [ x n − 1 + ( x n − 1 )   m o d   g ( x ) x n − 2 + ( x n − 2 )   m o d   g ( x ) ⋮ x n − i + ( x n − i )   m o d   g ( x ) ⋮ g ( x ) ] = [ 1 0 ⋯ 0 r 1 , 1 r 1 , 2 ⋯ r 1 , n − k 0 1 ⋯ 0 r 2 , 1 r 2 , 2 ⋯ r 2 , n − k ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 0 0 ⋯ 1 r k , 1 r k , 2 ⋯ r k , n − k ] G(x)=[\begin{array}{c} x^{n-1}+(x^{n-1})_{\bmod g(x)} \\ x^{n-2}+(x^{n-2})_{\bmod g(x)} \\ \vdots \\ x^{n-i}+(x^{n-i})_{\bmod g(x)} \\ \vdots \\ g(x) \end{array}]=[\begin{array}{cccccccc} 1 & 0 & \cdots & 0 & r_{1,1} & r_{1,2} & \cdots & r_{1, n-k} \\ 0 & 1 & \cdots & 0 & r_{2,1} & r_{2,2} & \cdots & r_{2, n-k} \\ \vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & 1 & r_{k, 1} & r_{k, 2} & \cdots & r_{k, n-k} \end{array}] G(x)=[xn1+(xn1)modg(x)xn2+(xn2)modg(x)xni+(xni)modg(x)g(x)]=[100010001r1,1r2,1rk,1r1,2r2,2rk,2r1,nkr2,nkrk,nk]

某 (7,4) 循环码的生成多项式是 g ( x ) = x 3 + x + 1 g(x)=x^{3}+x+1 g(x)=x3+x+1 , 求系统码的生成矩阵。

解:
( x 6 )   m o d   g ( x ) = x 2 + 1 ( x 5 )   m o d   g ( x ) = x 2 + x + 1 ( x 4 )   m o d   g ( x ) = x 2 + x a r r o w G = [ 1 0 0 0 1 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0 1 0 1 1 ] \begin{array}{l} (x^{6}) \bmod g(x)=x^{2}+1 \\ (x^{5}) \bmod g(x)=x^{2}+x+1 \\ (x^{4}) \bmod g(x)=x^{2}+x \end{array} \quad arrow G=[\begin{array}{lllllll} 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \end{array}] (x6)modg(x)=x2+1(x5)modg(x)=x2+x+1(x4)modg(x)=x2+xarrowG=[1000010000100001111001111101]

循环码的监督 (校验) 矩阵

关系: G H T = 0 \boldsymbol{G} \boldsymbol{H}^{T}=\mathbf{0} GHT=0

a. 监督矩阵构造:由性质 x n + 1 = g ( x ) h ( x ) x^{n}+1=g(x) h(x) xn+1=g(x)h(x) ;
h ( x ) = h k x k + h k − 1 x k − 1 + … + h 1 x + h 0 H = [ h 0 h 1 ⋯ h k 0 ⋯ 0 0 h 0 h 1 ⋯ h k ⋯ 0 ⋮ ⋮ 0 0 ⋯ h 0 h 1 ⋯ h k ] \begin{array}{l} h(x)=h_{k} x^{k}+h_{k-1} x^{k-1}+\ldots+h_{1} x+h_{0} \\ H=[\begin{array}{ccccccc} h_{0} & h_{1} & \cdots & h_{k} & 0 & \cdots & 0 \\ 0 & h_{0} & h_{1} & \cdots & h_{k} & \cdots & 0 \\ & \vdots & & & & \vdots & \\ 0 & 0 & \cdots & h_{0} & h_{1} & \cdots & h_{k} \end{array}] \\ \end{array} h(x)=hkxk+hk1xk1++h1x+h0H=[h000h1h00h1hkh00hkh100hk]
b. 利用循环码的特点来确定监督矩阵 H :

由于 (n, k) 循环码中 g(x) 是 x n + 1 x^{n+1} xn+1 的因式, 因此可令: h ( x ) = x n + 1 g ( x ) = h k x k + h k − 1 x k − 1 + ⋯ + h 1 x + h 0 h(x)=\frac{x^{n}+1}{g(x)}=h_{k} x^{k}+h_{k-1} x^{k-1}+\cdots+h_{1} x+h_{0} h(x)=g(x)xn+1=hkxk+hk1xk1++h1x+h0 监督矩阵表示为:

H ( x ) = [ x n − k − 1 h ∗ ( x ) x n − k − 2 h ∗ ( x ) ⋮ x h ∗ ( x ) h ∗ ( x ) ] H(x)=[\begin{array}{c} x^{n-k-1} h^{*}(x) \\ x^{n-k-2} h^{*}(x) \\ \vdots \\ x h^{*}(x) \\ h^{*}(x) \end{array}] H(x)=[xnk1h(x)xnk2h(x)xh(x)h(x)]

h ∗ ( x ) = h 0 x k + h 1 x k − 1 + h 2 x k − 2 + ⋯ + h k − 1 x h^{*}(x)=h_{0} x^{k}+h_{1} x^{k-1}+h_{2} x^{k-2}+\cdots+h_{k-1} x h(x)=h0xk+h1xk1+h2xk2++hk1x

参考文献:文章来源地址https://www.toymoban.com/news/detail-737085.html

  1. Proakis, John G., et al. Communication systems engineering. Vol. 2. New Jersey: Prentice Hall, 1994.
  2. Proakis, John G., et al. SOLUTIONS MANUAL Communication Systems Engineering. Vol. 2. New Jersey: Prentice Hall, 1994.
  3. 周炯槃. 通信原理(第3版)[M]. 北京:北京邮电大学出版社, 2008.
  4. 樊昌信, 曹丽娜. 通信原理(第7版) [M]. 北京:国防工业出版社, 2012.

到了这里,关于循环码生成矩阵与监督 (校验) 矩阵的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 第8章 特征矩阵(矩阵相似、最小多项式、特征矩阵相似、不变因子、初等因子和若当标准型)

    相似有相同的特征多项式,相同的特征值,相同的迹,A的行列式即det(A)也相同,相同的最小多项式,相同的秩。 从而求A的迹(特征值)转化为另一个矩阵的迹(特征值)。 例: (1)AB都正定,则tr(AB) 0,A正定,则有可逆阵P: 由于B正定,所以特征值都大于0,所以AB的迹大于

    2024年02月05日
    浏览(61)
  • 曲线生成 | 基于多项式插值的轨迹规划(附ROS C++/Python/Matlab仿真)

    🔥附C++/Python/Matlab全套代码🔥课程设计、毕业设计、创新竞赛必备!详细介绍全局规划(图搜索、采样法、智能算法等);局部规划(DWA、APF等);曲线优化(贝塞尔曲线、B样条曲线等)。 🚀详情:图解自动驾驶中的运动规划(Motion Planning),附几十种规划算法 多项式插值(polynomial

    2024年02月03日
    浏览(36)
  • AA@有理系数多项式@整系数多项式@本原多项式@有理多项式可约问题

    有理数域上一元多项式的因式分解. 作为 因式分解定理 的一个特殊情形,我们有结论: 每个次数大等于1的 有理系数多项式 都能 唯一地 分解成 不可约的有理系数多项式 的乘积. 有理数域版本中,从一般数域具体到了\\\" 有理系数 \\\" 我们讨论多项式的时候,都假设多项式是在某个数

    2024年02月16日
    浏览(49)
  • P4725 【模板】多项式对数函数(多项式 ln)

    洛谷P4725 【模板】多项式对数函数(多项式 ln) 题目大意 给你一个 n − 1 n-1 n − 1 次多项式 A ( x ) A(x) A ( x ) ,求一个   m o d   x n bmod x^n mod x n 下的多项式 B ( x ) B(x) B ( x ) ,满足 B ( x ) ≡ ln ⁡ A ( x ) B(x)equiv ln A(x) B ( x ) ≡ ln A ( x ) 。 在   m o d   998244353 bmod 998244353 mo

    2024年02月03日
    浏览(54)
  • 用链表表示多项式,并实现多项式的加法运算

    输入格式: 输入在第一行给出第一个多项式POLYA的系数和指数,并以0,0 结束第一个多项式的输入;在第二行出第一个多项式POLYB的系数和指数,并以0,0 结束第一个多项式的输入。 输出格式: 对每一组输入,在一行中输出POLYA+POLYB和多项式的系数和指数。 输入样例: 输出样例: 本

    2024年02月07日
    浏览(66)
  • 基于FPGA的LFSR16位伪随机数产生算法实现,可以配置不同的随机数种子和改生成多项式,包含testbench

    目录 1.算法仿真效果 2.算法涉及理论知识概要 3.Verilog核心程序 4.完整算法代码文件 vivado2019.2仿真结果如下:           LFSR(线性反馈移位寄存器)提供了一种在微控制器上快速生成非序列数字列表的简单方法。生成伪随机数只需要右移操作和 XOR 操作。LFSR 完全由其多项式

    2024年02月11日
    浏览(42)
  • 【C 数据结构】 用单链表存储一元多项式,并实现两个多项式相加运算。

    本次代码纯c语言,可以支持输入两个多项式的项式、系数、指数。 实验目的: 1 掌握单链表的基本工作原理; 2 实现链式存储下的两个多项式的相加。 实验步骤 1 定义链式存储的数据结构 2 完成多项式的初始化,即给多项式赋初值 3 完成多项式的输出 4 实现多项式的相加及结

    2024年02月06日
    浏览(46)
  • 牛顿插值法、拉格朗日插值法、三次插值、牛顿插值多项式、拉格朗日插值多项式

    两点式线性插值 调用Matlab库函数 拉格朗日二次插值: 牛顿二次插值 结果分析:通过对比不同插值方法,可以看到在一定范围内(高次会出现龙格现象),插值次数越高,截断误差越小(插值结果越接近于真实函数值);同时,对于相同次数的插值,由于不同的插值方法它们

    2024年02月11日
    浏览(45)
  • 多项式承诺:KZG

    参考文献: Merkle, R. ”Protocols for Public Key Cryptosystems.” Proc. 1980 Symp. on Security and Privacy, IEEE Computer Society (April 1980), 122-133. Benaloh J, Mare M. One-way accumulators: A decentralized alternative to digital signatures[C]//Workshop on the Theory and Application of of Cryptographic Techniques. Springer, Berlin, Heidelberg, 1993

    2024年02月04日
    浏览(55)
  • 多项式拟合

    文章内容部分参考: 建模算法入门笔记-多项式拟合(附源码) - 哔哩哔哩 (bilibili.com) (9条消息) 数学建模——人口预测模型 公有木兮木恋白的博客-CSDN博客 数学建模人口预测模型 多项式拟合是数据拟合的一种,与插值有一定区别(插值要求曲线经过给定的点,拟合不一定经

    2024年02月04日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包