11.2译码和纠错(Decoding and Error Correction) |
您所在的位置：网站首页 › 信息论最大似然译码准则 › 11.2译码和纠错(Decoding and Error Correction) |
11.2译码和纠错(Decoding and Error Correction)
|
11.2译码和纠错(Decoding and Error Correction)
译码函数\(d:B^n -> B^m\)被叫做与编码函数e相关联的译码函数，意思是\(d o e = 1_{B^m}\) 1.显然，译码函数必须是个满射函数，这样才能保证每个码字都能解码 2.译码函数不能保证每个码字都正确译中 例如:如果d是译奇偶校验码的 d(10010) = 1001 and d(11001) = 1100(不一定译正确) 再例如:e是三倍编码函数，那么其相应的译码是如此定义的:
让接收的码字用与其海明距离最小的正确码字来近似(不一定是一定正确的) 定理1: 和运输错误为k的最小距离至少为k+1相比，(e, d)能纠错为至多k的最小距离要求为2k+1(显然) 构建最大似然译码函数定理2: 设G的子有限群K，K的任何左(右)陪集的元素个数和K的元素个数相等 构造并证明一个从K -> aK双射的函数即可
令e是从\(e^m -> e^n\)的群编码，那么\(N = \{ e(B^m)\}\) = \(\{ x^{(1)},x^{(2)},...,x^{(2^m)}\}\)是\(B^n\)的子群，这为我们构造陪集头创造了条件 陪集头(Coset leader)知道这个方法，你最好先知道以下知识: 一个子群的所有左陪集要么相等，要么相交为∅ 所有左陪集的元素个数是相等的(下面会证明) 所有属于xH里面的元素(如a)，其左陪集 = xH 我们希望求出得到的和码字\(x_t\)的海明距离最近的代码字 ⊕运算有这样的性质: a ⊕ b = c ==> a ⊕ c = b, b ⊕ c = a假设传输的代码字x = e(b),而我们接受到的码字是\(x_t\) N对于\(x_t\)的左陪集: \(x_t ⊕ N = \{ε_1, ε_2, ... , ε_{2^m}\}\)，其中\(ε_i = x_t ⊕ x^{(i)}\)如果\(ε_j\)是权最小的陪集元素(Coset member)，那么我们就说相应的\(x_j\)是最接近\(x_t\)的(这个\(x_j\)也就是我们要求的)，我们称\(ε_j\)为陪集头(Coset leader) 于是，我们有了以下通过陪集头的译码步骤: 利用子群\(N = e(B^m)\)求\(B^n\)中所有码字的左陪集 对于每个陪集求最小权值的陪集头(\(ε_j\)) 对于接收到的码字\(x_t\)，先找到其所属的陪集和对应的陪集头 通过(3)中找到的陪集头ε,我们用ε ⊕ \(x_t\)来得到最接近的代码字x(运用知识点5)
特征值法 |
【本文地址】
今日新闻 |
推荐新闻 |