信道编码

信道编码卢超2016.10.19目录2■信道编码基本概念■经典信道编码●汉明码●卷积码■交织技术●矩阵交织●卷积交织■新型信道编码●Turbo●LDPC●Polar■信道编码的定义●信道编码又称差错控制编码，是通过在被传输数据中按照一定规则引人冗余（监督码元）来避免数字数据在传送过程中出现误码。■理论依据：Shannon信道编码定理●对于给定的有干扰信道，若其信道容量为C，只要发送端以低于C的速率R发送信息，则一定存在一种编码方法，随着码长n的增加且接收端采用最大似然译码时，误码率按指数下降到任意小的值。E(R)称为误差指数，n编码长度，R信息发送速率信道编码的基本概念3()nERBERe■信道编码理论的相关概念●码重：二进编码序列V中1的个数,表示为W(V)●码距：两个等长码组V1，V2中对应码位上不同二进制码元的个数，记作d(V1,V2)●最小码距(汉明距离)：对于某种编码，所含的全部码组之间的最小距离称为汉明距离，记作汉明距离直接决定着编码算法的检错和纠错能力，汉明距离越大，说明码字间的最小差别越大，抗干扰能力越强。●汉明距离与检错纠错能力检测e个错误纠正t个错误检测e个错误，同时纠正t个错误(et)信道编码基本概念4(1,2)(12)dVVWVV经典信道编码5■分组码之汉明码●1950年，R.Hamming和M.Golay提出了第一个实用的差错控制编码方案，极大地推动了编码理论这一应用数学分支的发展。通常认为是Hamming提出了第一个差错控制码。汉明码可记作（n,k）。k是信息码的位数，n是码组长度。1nc2ncrnc1rc2nc0c码长n=k+rk个信息位r个监督位经典信道编码6■分组码之汉明码●汉明码（n,k）编码理论码长监督位信息位码率●汉明码是一种能纠正单个随机错误且编码效率较高的线性分组码。常用的汉明码有（7，4）码，（15，11）码等，以前者来说明汉明码的编码方法。经典信道编码7■分组码之汉明码●汉明码（7，4）编码方法设码字为a6a5a4a3a2a1a0，规定校验关系（不唯一）a6+a5+a4+a2=0a6+a5+a3+a1=0a6+a4+a3+a0=00001001101010101100101110123456aaaaaaa矩阵形式,再由监督矩阵得到生成矩阵G这样，G在发送端用于生成汉明码，H在接收端进行码组的检错和纠错。卷积码的介绍8■卷积码是由P.Elias于1955年提出的一种非分组码，其性能优于分组码，且运算较简单。■与分组码的不同之处：①分组码的监督位完全由当前输入的信息段决定；卷积码的的监督码元不仅和当前的信息段有关，而且和前面的N-1个信息段有关，即一个卷积码组中的监督码元监督着N个信息段。②卷积码的编码和译码过程都是连续进行的，这样可以获得相对比较小的编译码延时。■卷积码的优势在系统条件相同的条件下，为达到相同译码性能，卷积码的信息块长度和码字长度都要比分组码的信息块长度和码字长度小，译码复杂性也小一些。卷积码可记作（n,k,N）,k为信息段，n为编码后的位数，N称为编码约束度。卷积码的编码原理9编码输出每次输入k比特1k…1k…1k…1k…………1…k…2k3kNk………………………12nNk级移存器n个模2加法器每输入k比特旋转1周卷积码的编码原理10■以(n,k,N)=(3,1,3)为例作具体分析c3c1c3𝑐1=𝑏𝑖𝑐2=𝑏𝑖⊕𝑏𝑖−2𝑐3=𝑏𝑖⊕𝑏𝑖−1⊕𝑏𝑖−2■在初始状态，移位寄存器均为0。例如输入为：11010，则对应的输出为111，110，010，100，001卷积码的码树图12000111001110011100010101000111001110011100010101c1c2c3000100111011001101110010c1c2c3111000001110c1c2c3信息位1101ba起点信息位000111c1c2c3abcdabcdabcdabcd上半部下半部10a状态bi-2bi-1a00b01c10d11abcdabcdcdab↑0↓1↓1↑0↑0↓1卷积码的状态转移图（类似于Markov链）12bdca1/1110/0000/0111/1001/1100/0010/0101/101状态bi-2bi-1a00b01c10d11■由状态转移图可见，状态a只能转移到状态b或c，状态b只能转移到状态c或d，等等。利用状态图可以方便地从输入信息位得到输出序列。abcd000000000000000111111111111111011011011001001100001110110110110010010010101101101100卷积码的网格图：状态图在时间上的展开13■虚线表示输入信息位为1时状态转变的路线，实线表示输入信息位为0时状态转变的路线。根据此图，若从初始态开始，输入信息位为11010，则能方便地得到输出序列是：111110010100001卷积码的解码算法14■1963年Massey提出的门限解码，这是一种利用码的代数结构的代数译码，对约束长度较短的卷积码最为有效，且解码设备简单，速度快，但其误码性能要比概率译码法差。■1961年Wozencraft提出，1963年由fano改进的序列译码，是基于码数图结构的一种准最佳的概率译码。■1967年Viterbi提出的Viterbi算法，这是基于码的网图Trellis基础上的一种最大似然译码算法。当码的约束长度较短时，它的效率比序列解码算法更高、速度更快，目前得到了广泛的应用，是一种最佳概率译码方法。可以说正是由于维特比算法的提出，才使得卷积码在通信系统中得到了极为广泛的应用，如GSM、3G、商业卫星通信系统等。卷积码的门限解码15■卷积码是一种线性码，因此有可能利用校正子指示接收码组中的错码位置，从而纠正错码。门限解码工作原理如下图所示。b6b1b2b3b4b5+信息移位寄存器输入D6D1D2D3D4D5校正子移位寄存器++门限电路重算监督位一级移位寄存器接收监督位校正子输出654321卷积码的维特比解码16■原理：维特比解码是将接收到的信号序列和所有可能的发送序列进行比较，依次计算它们之间的汉明距离，把汉明距离最小的序列作为发送序列。若发送一个k位序列，则有2𝑘种可能发送的序列，就需要大量的存储空间。维特比算法对此做了简化，即它把接收码字分段累接处理，每接收一段码字，计算、比较一次，保留码距最小的幸存路径，直至译完整个序列。■仍以前述的（3，1，3）卷积码为例讨论维特比算法原理。●设信息位是：1101，则编码后的发送序列是111110010100，假设接收序列为111010010110,即第四位出现错码。由于发送序列的约束长度L=nN，因此先考察前9bit：“111010010”。为此需找出可能的发送序列。●回到之前的网格图，可见沿路径的每一级有4种状态，每种状态共2条可达路径，所以一共是4*2=8条达到路径，即8个可能发送的序列。卷积码的维特比解码17●计算这8条路径与接收序列的汉明距离。对于某个状态的两条路径，留下汉明距离较小的路径。序号路径对应序列汉明距离是否保留1aaaa0000000005否2abca1110010113是3aaab0000001116否4aaab1110011004是5aabc0001110017否6abdc1111100101是7aabd0001110016否8abdd1111101014是卷积码的维特比解码18●继续考察接收序列的后三位“110”。前面已经筛选出来了4条路径，现在再增加一级，则一共有8条可能的路径，继续计算它们与发送序列的汉明距离，结果如下表所示。序号路径原汉明距离新增距离总汉明距离是否保留1abca+a325否2abdc+a123是3abca+b314否4abdc+b112是5abcb+c437否6abdd+c415是7abcb+d404否8abdd+d426是●我们选取汉明距离最小的路径：abdc+b，对应的序列是111110010100，解码出的原序列是：1101，这样就纠正了1位错码。第三节交织技术19■什么是交织？交织从本质上来说就是最大限度的改变信息结构而不改变信息内容，使信道传输过程中所产生的突发错误最大限度的分散化。■交织有何作用？在移动通信中，信道的干扰、衰落等产生较长的突发误码，采用交织就可以使误码离散化，接收端用纠正随机差错的编码技术消除随机差错，能够改善整个数据序列的传输质量。■有哪些交织方法？●矩阵交织●卷积交织矩阵交织器20■在发送端，将经过信道编码的数据按行（列）存入，按列（行）读出；在接收端执行相反的操作（解交织），即按列存入，按行读出。16111621271217223813182349141924510152025xxxxxxxxxxxxxxxxxxxxxxxxx信道传输产生突发错误14611131618223578910121415171921230222425--xxxxxxxxxxxxxxxxxxxxxxxxx按列存入交织器123232425xxxxxx……16111621271217223813182349141924510152025--xxxxxxxxxxxxxxxxxxxxxxxxx按行从交织器中读出27121722389141924510152161116211318254023--xxxxxxxxxxxxxxxxxxxxxxxxx按行存入交织器27121722389141924510151611162113182342025xxxxxxxxxxxxxxxxxxxxxxxxx按列从交织器中读出■显然，编码序列经过交织处理后，如果发生突发错误而造成大量错码，就可以将突发错误转换为不连续的偶然发生的独立的随机错误，从而有利于纠错。矩阵交织器21■矩阵交织处理的方法●将需要进行交织处理的编码分成长度为L的子组，并有：L=M(列)*N(行)■矩阵交织的缺点●交织和去交织的处理会造成2MN个符号的延迟。●周期为M个符号的单个独立错误经过交织和去交织后，可能变成一个突发错误。例如在上例中，序列在传输时并没有发生突发性的错误，而是发生了随机错误，解交织器接收码元为那么经过解交织后，得到的码元将是这说明交织也可能会造成独立错误变成突发错误的特殊情况。11116212121722313182341419245152025678910xxxxxxxxxxxxxxxxxxxxxxxxx12345111213614151617181927891002122232425xxxxxxxxxxxxxxxxxxxxxxxxx卷积交织器22■卷积交织处理的方法比矩阵交织复杂，以一个例子来说明23x4xx1123xxx4xxx1xxx1xxxxxx交织器解交织器67384x55672xx8xx25x2x51xxxxx交织器解交织器10117128499101163x12x369362951xxxx交织器解交织器卷积交织器23■交织器的输入依次是1~16，输出为：1xxx52xx963x131074解交织器的输出为:xxxxxxxxxxxx123410117128499101163x12x369362951xxxx交织器解交织器1415111612813131415107416471013710613954321交织器解交织器■一般来说，第1个移存器的容量可以是k比特，……，第N个移存器的容量则是Nk比特。与矩阵交织法相比，卷积交织法端到端的总时延和总存储容量均是kN(N+1)，是矩阵交织法的一半。GSM中的交织24■在GSM系统中，语音数字信号经过信道编码后进行交织，交织分为两次，第一次交织为内部交织，第二次交织为块间交织。●内部交织语音编码器和信道编码器将每一20ms话音数字化并编码，生成456个比特。首先对这456个进行内部交织，即将456个比特分成8组，每组