线性分组码编码与译码(MATLAB实现)

这篇具有很好参考价值的文章主要介绍了线性分组码编码与译码(MATLAB实现)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

线性分组码的定义

分组码是对信息序列分段编码。若对包含 k 个信息元的信息组 M
循环码快速阵列译码和标准阵列译码对比,matlab,算法,线性代数,预编码算法,安全按照一定的编码规则产生包括 n 个码元的码组 C
循环码快速阵列译码和标准阵列译码对比,matlab,算法,线性代数,预编码算法,安全编码规则定义为:循环码快速阵列译码和标准阵列译码对比,matlab,算法,线性代数,预编码算法,安全
如果 fi(·),i = 0,1,…,n-1 均为线性函数,则称 C 为线性分组码。线性分组码一般用 (n,k,d)码表示,其中 n 为码长,k 为信息组长度,d 为码的最小距离。
实际上,(n,k,d)线性分组码是 q 元有限域 GF(q)n 维线性空间 Vn 中的一个 k 维子空间 Vn,k,如下图所示:
循环码快速阵列译码和标准阵列译码对比,matlab,算法,线性代数,预编码算法,安全如果信息组 M 和码组 C 的所有元素均取自二元有限域 GF(2)(即{0,1}),则称为二元线性分组码。
二元线性分组码的编码过程实际上就是从包含 2k 个信息的 Vk 空间包含到 2n 个码字的 C 空间(Vn,k)的映射过程。也即 GF(2) 上信息组 M 到码字 C 的映射。如果编码函数都是线性的,则为线性分组码。
对于二元线性分组码,有如下结论:
①(n,k,d)线性分组码的最小距离 d 等于其非零码字的最小重量,即:循环码快速阵列译码和标准阵列译码对比,matlab,算法,线性代数,预编码算法,安全②GF(2) 上(n,k,d)线性分组码中任何两个码字 C1 和 C2 之间满足关系:
循环码快速阵列译码和标准阵列译码对比,matlab,算法,线性代数,预编码算法,安全③GF(2) 上线性分组码的任意三个码字之间的汉明距离满足如下三角不等式:
循环码快速阵列译码和标准阵列译码对比,matlab,算法,线性代数,预编码算法,安全④任何(n,k,d)线性分组码的码字重量或者全部为偶数,或者重量为奇数的码字个数与重量为偶数的码字个数相等。
⑤任何(n,k,d)线性分组码的最大最小距离等于 n-k+1,即 d ≤ n-k+1。

例:(7,4,3)线性分组码。
下表给出了(7,4,3)线性分组码的信息组和码字的对应关系。

信息组 码字 信息组 码字
0000 00000000 1000 1101000
0001 1010001 1001 0111001
0010 1110010 1010 0011010
0011 0100011 1011 1001011
0100 0110100 1100 1011100
0101 1100101 1101 0001101
0110 1000110 1110 0101110
0111 0010111 1111 1111111

通过计算,可以验证上述 5 点结论的正确性。

线性分组码的生成矩阵

由于(n,k,d)二元线性分组码是 GF(2) 上 n 维线性空间的一个 k 维子空间,因此在码集合中一定可以找到一组码字 gk-1,gk-2,…,g0,使得所有码字都可以由这组码字的线性组合表示,即:循环码快速阵列译码和标准阵列译码对比,matlab,算法,线性代数,预编码算法,安全也即码空间(k 维子空间 Vn,k)完全可以由这个 k 个独立码字 gi i = k-1,k-2,…,0 所组成的基底张成。gi i = k-1,k-2,…,0 是 k 维线性空间的一组基底(互不相关的行向量),若记 gi = (gi,0,gi,1,…,gi,n-1),则将这组码字写成矩阵形式,即为(n,k,d)线性分组码的生成矩阵 G。
循环码快速阵列译码和标准阵列译码对比,matlab,算法,线性代数,预编码算法,安全(n,k,d)线性分组码的生成矩阵 G是一个 k*n 的二元矩阵。
例:(7,4,3)线性分组码中找到 4 个线性无关的行向量来构成生成矩阵 G。如下所示:
循环码快速阵列译码和标准阵列译码对比,matlab,算法,线性代数,预编码算法,安全

线性分组码的检验矩阵

根据线性代数知识,生成矩阵 G 是由一个 k 个线性无关的行向量构成的,因此一定存在一个由 n-k 个线性无关的行向量组成的矩阵 H 与之正交,即:
循环码快速阵列译码和标准阵列译码对比,matlab,算法,线性代数,预编码算法,安全矩阵 H 是一个 (n-k)*n 的二元矩阵,即线性分组码的校验矩阵。一般情况下,线性分组码的校验矩阵 H 可以表示为:
循环码快速阵列译码和标准阵列译码对比,matlab,算法,线性代数,预编码算法,安全
例:前述(7,4,3)线性分组码的校验矩阵为:
循环码快速阵列译码和标准阵列译码对比,matlab,算法,线性代数,预编码算法,安全
实际上,(n,k,d)线性分组码编码的目的就是如何在 n 维线性空间 Vn 中找到编码要求的、由 2k 个向量组成的 k 维子空间 Vn,k。这相当于建立一组线性方程,已知系数和未知系数的个数分别为 k 个和 n-k 个,且使得码字恰好最小距离为 d。
建立的线性方程组为 :
循环码快速阵列译码和标准阵列译码对比,matlab,算法,线性代数,预编码算法,安全写成矩阵和行向量的乘积形式,有
循环码快速阵列译码和标准阵列译码对比,matlab,算法,线性代数,预编码算法,安全根据生成矩阵 G 的定义,对于系统吗,矩阵 G 的 k 列可以组成一个 k 维的单位矩阵 Ik,如果这个单位矩阵出现在矩阵 G 的最左边 k 列(也可以是最右边的 k 列),则码字 C 的前 k 位就是信息元。

线性分组码的纠错能力

对于(n,k,d)线性分组码,其检纠错能力与码字的最小距离直接相关。一般情况下,有如下结论:
①检测 e 个随机错误,则要求码的最小距离 d ≥ e+1。
②纠正 t 个随机错误,则要求码的最小距离 d ≥ 2t+1。
③纠正 t 个同时检测 e 个随机错误(e ≥ t),则要求码的最小距离 d ≥ t+e+1。

线性分组码编码

根据生成矩阵 G 进行线性分组码的编码过程非常简单,信息组 M 、码组 C 与生成矩阵 G 之间的关系为: 循环码快速阵列译码和标准阵列译码对比,matlab,算法,线性代数,预编码算法,安全例:假设 M = (1 1 1 1),前述(7,4,3)线性分组码的编码过程为:
循环码快速阵列译码和标准阵列译码对比,matlab,算法,线性代数,预编码算法,安全

线性分组码译码

编码输出码字在信道上传输时可能产生一定的码元错误,这些码元错误称为错误图样。假设发送码字为 C,信道产生的错误图样为 E,则接收码字为 R = C+E。在前向纠错方式中,译码器的作用就是如何根据接收码字 R 来估计错误图样 E,进而得到对发送码字 C 的估计。
线性分组码的译码主要有伴随式译码和标准阵列译码两种方法。

伴随式译码

伴随式 S 定义为:
循环码快速阵列译码和标准阵列译码对比,matlab,算法,线性代数,预编码算法,安全式中,S 是 n-k 维列向量。根据发送码字 C 与校验矩阵 H 之间的关系以及发送码字 C 与接收码字 R 之间的关系,有:
循环码快速阵列译码和标准阵列译码对比,matlab,算法,线性代数,预编码算法,安全由此可以看出,伴随式的值仅与信道错误图样有关,与发送码字无关。如果在信道传输过程中无错误发生,即 E = 0,则 S = 0;否则 S ≠ 0。
伴随式译码算法的基本思想就是根据伴随式 S 的值来估计错误图样 E。如果将校验矩阵 H 写成列向量的形式:
循环码快速阵列译码和标准阵列译码对比,matlab,算法,线性代数,预编码算法,安全则有
循环码快速阵列译码和标准阵列译码对比,matlab,算法,线性代数,预编码算法,安全即伴随式 S 是校验矩阵 H 中列向量的线性组合。对于错误图样 E,码元中第 j 位发生错误时其值 ej = 1,否则 ej = 0。因此伴随式 S 的值实际上是出错码元对应的校验矩阵 H 的列向量的模 2 和的结果。
在线性分组码的纠错能力范围内,如果能够确定伴随式 S 的值是校验矩阵 H 的那个列向量或哪几个列向量的模 2 和,则可以确定错误图样 E,进而实现译码。因此,如果要使一个(n,k,d)线性分组码能够纠正小于等于 t 个错误,则要求小于等于 t 个错误的所有可能组合的错误图样对应的伴随式 S 均不相同,这等价于:
如果
循环码快速阵列译码和标准阵列译码对比,matlab,算法,线性代数,预编码算法,安全则要求
循环码快速阵列译码和标准阵列译码对比,matlab,算法,线性代数,预编码算法,安全即如果包含小于等于 t 个错误的错误图样 Ei ≠ Ej,则相应的伴随式必须满足 S(Ei) ≠ S(Ej)。
综上所述,伴随式译码的主要步骤如下:
①根据接收码字 R,利用公式 S = RHT 计算伴随式 S。
②根据伴随式 S,在码字纠错能力范围内得到错误图样 E 的估计 E^。
③估计发送码字 C^ = R+E^。
需要说明的式,对于二元码,上述所有运算都是在 GF(2) 中进行的。另外,如果在接受码字 R 中出现的错误数大于线性分组码的纠错能力 t,则可能产生不正确的译码结果。
例:对于前述(7,4,3)线性分组码,假设发送码字为全 0 码字 C,接收码字为 R = (0010000),则计算得到的伴随式为:
循环码快速阵列译码和标准阵列译码对比,matlab,算法,线性代数,预编码算法,安全伴随式 S 与校验矩阵 H 的第 4 列完全相同,因此估计的错误图样为 R = (0001000),译码输出 C = R+E = (0001000),译码错误。这是因为该线性分组码的最小距离为 3,纠错能力为 1。接收码字中出现了多余 1 个错误,超出了其纠错能力,因此无法实现正确译码。

标准阵列译码

(n,k,d)线性分组码的 2k 个码字构成了 n 维线性空间的一个 k 维子空间,即一个子群。以子群为基础可以将整个 n 维线性空间的所有 2n 个元素划分成 2k 个陪集,如下标准阵列译码表所示:
循环码快速阵列译码和标准阵列译码对比,matlab,算法,线性代数,预编码算法,安全在标准阵列译码表中,2k 个码字放在第一行,该子群的恒等元素 C1 (全0码字)放在最左边,然后在禁用码字集合中选择一个 E2 放置在下面一行,并计算预期所有码字的模 2 和,放在第 2 行,构成码空间的一个陪集。类似的选择 E3、 E4、…、 E2^(n-k) 并构成 2n-k 个陪集。其中第 1 列的向量称为陪集首。
标准阵列译码的关键问题式如何确定陪集首。一般原则是保证译码器能够纠正出现可能性最大的错误图样,即重量最小的错误图样,所以选择重量最小的 n 重向量作为陪集首,这样可以保证安排的译码表使得 Ci+Ej 与 Ci 的汉明距离最小,实现最小距离译码。在二元对称信道条件下等效于最大似然译码。译码时,如果接收码字 R 落到标准阵列译码表中的第 i 列,则译码输出就为相应的 Ci。如果发送码组为 Ci,则译码正确,否则译码错误。

MATLAB仿真实现

1、线性分组码的编码

code = rem(msg*G,2)

其中,G 为线性分组码的生成矩阵,msg 为传入的信息数据,2 表示二元域即 GF(2)。
2、线性分组码的译码文章来源地址https://www.toymoban.com/news/detail-791704.html

function decoded = decoder(n,k,rec,H,d)
% n:输入1:码字长度
% k:输入2:信息组长度
% rec:输入3:译码器接收的硬判决码字
% H:输入4:分组码的校验矩阵
% d:输入5:分组码的最小距离

% decoded:输出1:译码输出码字

[M,N] = size(H);
t = fix((d-1)/2);
% 初始化并计算不同个数H矩阵列向量的所有组合的个数
num = zeros(1,t);
for idx = 1:t
	num(idx) = factorial(n)/factorial(n-idx)/factorial(idx);
	end
	maxnum = max(num);
	out = zeros(t,maxnum,t);
	out(1,1:num(1),1) = 1:n;
	out = compound(out,n,num,t,1); % 计算伴随式组合函数
	Hcom = zeros(1,n-k);
	E = zeros(1,N);
	S = rem(rec*H',2);
	if find(S)
		for err = 1:t
			for idx = 1:num(err)
				Hcom = zeros(1,n-k);
				for j = 1:err
					Hcom = rem(Hcom + H(:,out(err,idx,j))',2);
				end
				if(sum(rem(S+Hcom,2)) == 0)
					E(out(err,idx,1:err)) = 1;
					decoded = rem(rec+E,2);
				end
			end
		end
	else
		decoded = rec;
	end
end

到了这里,关于线性分组码编码与译码(MATLAB实现)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • P02114065刘浩宇,P02114070程韩奇,P02114066吴其,P02114068张璐——深入理解线性分组码的生成矩阵和校验矩阵定义及其关系

    目录 前言 线性分组码 定义 性质 生成矩阵和校验矩阵 生成矩阵 生成矩阵的定义 生成矩阵的特性 校验矩阵 校验矩阵的定义 校验矩阵的特性 生成矩阵和校验矩阵的关系 由于移动通信存在干扰和衰落,在信号传输过程中将出现差错,故对数字信号必须采用纠、检错技术,即纠

    2024年02月03日
    浏览(41)
  • BCH编码与译码(MATLAB实现)

    BCH码是由Bose、Chandhari 和 Hocquenhem 分别独立提出的一种能够纠正多个随机错误的循环码。 BCH 码的定义:给定任一有限域 GF(q)及其扩域 GF(q m )(其中 q 为素数或素数幂),m 为某一正整数,若码元取自 GF(q) 循环码的生成多项式 g(x) 的根集合 R 中有 σ-1 个连续根 α m0 , α m0+1 ,

    2024年01月20日
    浏览(42)
  • 单载波频域均衡matlab仿真,包括卷积编码维特比译码,矩阵交织,QPSK调制解调,导频插入,MMSE-FDE频域均衡

    目录 1.算法描述 2.仿真效果预览 3.MATLAB核心程序 4.完整MATLAB         频域均衡是从校正系统的频率特性出发,利用一个可调滤波器的频率的频率特性去补偿信道或系统的频率特性,使包括可调滤波器在内的基带系统的总特性接近无失真传输条件。频域均衡是在频域上进行的,

    2023年04月08日
    浏览(48)
  • 信道编码---RS编码与译码原理

    本文介绍了RS编码以及译码的原理。 本文的内容基本上都来自刘梦欣的《基于FPGA的RS编译码研究与设计》,大家可以通过知网找到这篇文章,链接在下面。对RS码的原理讲解非常清楚,如果要看的话可以结合第2和第3部分一起看更好懂。我的整理也是比较粗略,因此没看懂的话

    2024年02月11日
    浏览(44)
  • 卷积编码和维特比译码

    卷积码是一种非分组码,通常适用于前向纠错。在分组码中,编码器产生的 n 个码元的一个码组,完全决定于这段时间中 k 比特输入信息。这个码组中的监督位仅监督本码组中 k 个信息位。卷积码在编码时虽然也是把 k 比特的信息段编成 n 个比特的码组,但是监督码元不仅和

    2024年02月08日
    浏览(40)
  • Polar码的编码思想以及SC译码算法

    1.3.1BEC信道 1.3.2信道联合极化编码思想 2009年在“IEEETransaction on Information Theory”期刊上发表论文详细地阐述了信道极化,并基于信道极化给出了一种新的编码方式,名称为极化码。从代数编码的角度来说,只要给定编码长度,极化码的编译码结构就唯一确定了;从概率编码的

    2024年02月06日
    浏览(39)
  • 【数据结构与算法】Huffman编码/译码(C/C++)

    利用哈夫曼编码进行信息通讯可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码;在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系

    2024年02月04日
    浏览(42)
  • MATLAB——PCM编译码实验

    1.掌握PCM编码原理和译码原理 2. 练习使用Matlab编程实现PCM编码和译码 3. 了解失真度的概念,能对译码结果进行失真度分析 脉冲编码调制 就是把一个时间连续,取值连续的模拟信号变换成时间离散,取值离散的数字信号后在信道中传输。脉冲编码调制就是对模拟信号先抽样,

    2024年02月02日
    浏览(32)
  • 遗传算法的编码方式以及MATLAB实现

    遗传算法原理以及matlab代码_matlab遗传算法代码_电气不会转控制的博客-CSDN博客 目录 前言 一、编码是什么? 二、二进制编码 1.整数区间 2.实数区间 3.多变量 4.运算操作(交叉,变异) 三、实数编码 1.实数编码的交叉操作 2.实数编码的变异操作  四、MATLAB代码实现 总结 提示

    2024年02月04日
    浏览(40)
  • Turbo编译码Matlab仿真解读 -- WuYufei_matlab

    吴雨霏博士版本的Turbo编译码仿真较为经典,以下就原码进行解读。 “ turbo_sys_demo.m ” 是程序的主体框架,Turbo编译码均在此程序展开。程序开始需要用户需要如下几个参数: 1)译码算法 :选择使用0:Log-MAP,1:SOVA     这是让用户选择使用何种Turbo译码算法。若Tubo为多次

    2023年04月22日
    浏览(31)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包