线性分组码的定义
分组码是对信息序列分段编码。若对包含 k 个信息元的信息组 M:
按照一定的编码规则产生包括 n 个码元的码组 C:
编码规则定义为:
如果 fi(·),i = 0,1,…,n-1 均为线性函数,则称 C 为线性分组码。线性分组码一般用 (n,k,d)码表示,其中 n 为码长,k 为信息组长度,d 为码的最小距离。
实际上,(n,k,d)线性分组码是 q 元有限域 GF(q) 上 n 维线性空间 Vn 中的一个 k 维子空间 Vn,k,如下图所示:
如果信息组 M 和码组 C 的所有元素均取自二元有限域 GF(2)(即{0,1}),则称为二元线性分组码。
二元线性分组码的编码过程实际上就是从包含 2k 个信息的 Vk 空间包含到 2n 个码字的 C 空间(Vn,k)的映射过程。也即 GF(2) 上信息组 M 到码字 C 的映射。如果编码函数都是线性的,则为线性分组码。
对于二元线性分组码,有如下结论:
①(n,k,d)线性分组码的最小距离 d 等于其非零码字的最小重量,即:②GF(2) 上(n,k,d)线性分组码中任何两个码字 C1 和 C2 之间满足关系:
③GF(2) 上线性分组码的任意三个码字之间的汉明距离满足如下三角不等式:
④任何(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,使得所有码字都可以由这组码字的线性组合表示,即:也即码空间(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。
(n,k,d)线性分组码的生成矩阵 G是一个 k*n 的二元矩阵。
例:(7,4,3)线性分组码中找到 4 个线性无关的行向量来构成生成矩阵 G。如下所示:
线性分组码的检验矩阵
根据线性代数知识,生成矩阵 G 是由一个 k 个线性无关的行向量构成的,因此一定存在一个由 n-k 个线性无关的行向量组成的矩阵 H 与之正交,即:
矩阵 H 是一个 (n-k)*n 的二元矩阵,即线性分组码的校验矩阵。一般情况下,线性分组码的校验矩阵 H 可以表示为:
例:前述(7,4,3)线性分组码的校验矩阵为:
实际上,(n,k,d)线性分组码编码的目的就是如何在 n 维线性空间 Vn 中找到编码要求的、由 2k 个向量组成的 k 维子空间 Vn,k。这相当于建立一组线性方程,已知系数和未知系数的个数分别为 k 个和 n-k 个,且使得码字恰好最小距离为 d。
建立的线性方程组为 :
写成矩阵和行向量的乘积形式,有
根据生成矩阵 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 之间的关系为: 例:假设 M = (1 1 1 1),前述(7,4,3)线性分组码的编码过程为:
线性分组码译码
编码输出码字在信道上传输时可能产生一定的码元错误,这些码元错误称为错误图样。假设发送码字为 C,信道产生的错误图样为 E,则接收码字为 R = C+E。在前向纠错方式中,译码器的作用就是如何根据接收码字 R 来估计错误图样 E,进而得到对发送码字 C 的估计。
线性分组码的译码主要有伴随式译码和标准阵列译码两种方法。
伴随式译码
伴随式 S 定义为:
式中,S 是 n-k 维列向量。根据发送码字 C 与校验矩阵 H 之间的关系以及发送码字 C 与接收码字 R 之间的关系,有:
由此可以看出,伴随式的值仅与信道错误图样有关,与发送码字无关。如果在信道传输过程中无错误发生,即 E = 0,则 S = 0;否则 S ≠ 0。
伴随式译码算法的基本思想就是根据伴随式 S 的值来估计错误图样 E。如果将校验矩阵 H 写成列向量的形式:
则有
即伴随式 S 是校验矩阵 H 中列向量的线性组合。对于错误图样 E,码元中第 j 位发生错误时其值 ej = 1,否则 ej = 0。因此伴随式 S 的值实际上是出错码元对应的校验矩阵 H 的列向量的模 2 和的结果。
在线性分组码的纠错能力范围内,如果能够确定伴随式 S 的值是校验矩阵 H 的那个列向量或哪几个列向量的模 2 和,则可以确定错误图样 E,进而实现译码。因此,如果要使一个(n,k,d)线性分组码能够纠正小于等于 t 个错误,则要求小于等于 t 个错误的所有可能组合的错误图样对应的伴随式 S 均不相同,这等价于:
如果
则要求
即如果包含小于等于 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),则计算得到的伴随式为:
伴随式 S 与校验矩阵 H 的第 4 列完全相同,因此估计的错误图样为 R = (0001000),译码输出 C = R+E = (0001000),译码错误。这是因为该线性分组码的最小距离为 3,纠错能力为 1。接收码字中出现了多余 1 个错误,超出了其纠错能力,因此无法实现正确译码。
标准阵列译码
(n,k,d)线性分组码的 2k 个码字构成了 n 维线性空间的一个 k 维子空间,即一个子群。以子群为基础可以将整个 n 维线性空间的所有 2n 个元素划分成 2k 个陪集,如下标准阵列译码表所示:
在标准阵列译码表中,2k 个码字放在第一行,该子群的恒等元素 C1 (全0码字)放在最左边,然后在禁用码字集合中选择一个 E2 放置在下面一行,并计算预期所有码字的模 2 和,放在第 2 行,构成码空间的一个陪集。类似的选择 E3、 E4、…、 E2^(n-k) 并构成 2n-k 个陪集。其中第 1 列的向量称为陪集首。
标准阵列译码的关键问题式如何确定陪集首。一般原则是保证译码器能够纠正出现可能性最大的错误图样,即重量最小的错误图样,所以选择重量最小的 n 重向量作为陪集首,这样可以保证安排的译码表使得 Ci+Ej 与 Ci 的汉明距离最小,实现最小距离译码。在二元对称信道条件下等效于最大似然译码。译码时,如果接收码字 R 落到标准阵列译码表中的第 i 列,则译码输出就为相应的 Ci。如果发送码组为 Ci,则译码正确,否则译码错误。
MATLAB仿真实现
1、线性分组码的编码文章来源:https://www.toymoban.com/news/detail-791704.html
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模板网!