（通信与信息系统专业论文）rayleigh信道中分组码网格译码及分组编码调制的研究.pdf

摘要 摘要 网格译码是实现分组码软判决译码的一个重要的研究方向 本文采用广义阵列码结构，实现简洁的网格构造及类似v i t e r b i 的译码。笔者着眼于长突发严重的移动信道，研究了r a y l e i g h 衰 落信道中分组码与这种准最大似然译码的结合及其在图象传输中 的应用。结果表明软判决译码的分组码能够在移动信道中进行有 效的差错控制，传输质量在很低的发射功率下也能得到保证。 ( 7 ，4 ，3 ) 和( 1 5 ，5 ，7 ) 被尝试用于移动信道图象传输系统中并有令 人满意的表现 厂 f 传统差错控制编码的最大缺陷就是可靠性和有效性的矛盾。 因为其纠错能力的提高是靠增加冗余位，因而不可避免的牺牲一 定的带宽编码调制的结合方案可以有效的解决这一矛盾因此 本文的第三章就基于广义阵列码的单级b c m 方案进行了研究此 方案首先将k 位信息分成n 组，满足： k = k o + k 1 + k 2 + + k n 一1 ，且k o k 1 ，k 1 = k 2 毫= k n 一2 ，k n 一】= 0 然后将每组信息映射到m 点的信号集中，每个信号点以k 。重 向量的形式表示：s i 2 ( xo x 1 ，x k o - 1 ) ， i 2 o - 2 z 。川 ti 1 - 0 解调以后经过一次6 a c 网格译码就恢复出原始信息。因此，这 r a y l e i g h 信道中分组码的网格详玛及分纽编码塑型的研蔓 种c f 方案的构造简单，实现复杂度较低。计算机仿真得到了此c m 方案在理想交织的r a y l e i g h 信道中性能，结果很令人满意。 首 先，与未编码的b p s k 和4 p s k 相比，在保证传输率基本不变的情况 下，( 8 ，4 ，4 ) 4 p s k 和( 1 5 ，9 4 ) 8 p s k 方案分别可获得2 5 d b 和2 0 d b 的编码增益。另外值得一提的是，( 2 1 ，13 ，4 ) 8 p s k 和 ( 15 ，9 ，4 ) 8 p s k 有相近的性能，但后者复杂度更低，因而对于同样 最小汉明距离的码字，我们应该更倾向于采用短码。 广义阵列码的单级c m 方案以其良好的性能，简单的结构和容 易实现的特点表现极大优势。但是深入的研究过程中我们发现 这一方案也存在两点缺陷是不可避而不谈的。首先，这种单级编 码调制方案没能充分利用信号集的分割原理，码字一旦确定就决 定了与其对应的调制方式。这种固定搭配不是欧氏空间的最佳c m 方案；其次，单级编码调制的传输率很低。例如( 1 q ，5 ，4 ) 4 p s k 的 传输率仅为i 。这是由g a c 的结构决定的。为了克服这两个缺陷， 我们把目光重新投向了多级编码调制系统 m l c ) 。虽然h u b e r 等 人从信息论的角度提出了多级编码系统的信道容量规则，但笔者 。 认为此规则有其自身的局限性。首先，它要求知道多级编码系统 各等价信道的信道容量，这在有些情况下是很难得到的。其次， 为了应用信道容量规则，作为分量码的分组码需要有很长的码长 摘要 以满足对码率的要求，这一点不可避免地导致译码复杂度和译码 延时的增加而且，h u b e r 的信道容量规则仅仅适用于采用多阶 段译码的多级编码系统。但多阶段译码中复杂度高及时延长的不 利因素使得它很难在实时通信中发挥作用。因而，我们有时会倾 - 向于各级的并行译码( p d l ) ，这时，信道容量规则将不再适用。 本文的第四和粒章正是针对这些缺陷，寻求r a y l e i h g 衰落 信道中低复杂度的有效编码调制方案。首先对多级g a c p d l 系统 进行了研究。通过u p ，b p 星座及其性能的比较，寻找到多级编码 系统中一种新的距离度量。它不仅考虑到集分割后各子集中信号 点间的距离，还考虑到同一级子集间的距离。以此距离为基础，提 出了分量码的选取准则。基于这种新的距离准则，我们构造了一 些广义阵列码作分量码的三级b c m 方案，模拟结果很好的证明了 我们的距离度量的有效性。i ， 、为了在提高性能的同时降低系统复杂度，本文还提出了一种新 的两级编码采用8 p s k 调制的m l c m s d 方案与传统三级编码8 p s k - 方案相比，这种结构有以下几点优势： 首先，简化了编码电路，因为只需两个编码器； 其次，缩短了译码过程的时延 另外因为译码只有两级，错误传播效应得到了缓解。 r a y l e i g h 信道中分组码的列格译码及分组编码调制的研究 而且，这种方法能力更多的信息提供增强的错误保护能力， 另外本文还致力于研究不等错误保护特性与系统整体性能的 折中，针对不同的通信业务，给出多种方案以满足对不等错误保 护与系统整体性能的要求。第壬章还对系统的硬件实现复杂度作 了粗浅的估计，对系统的实用化会有所帮助。 关锘柳广义阵列码，网格译码，分组编码调制，移动信道，距离度量 a b s t r a c t t r e l l i sd e c o d i n gi sa ni m p o r t a n tr e s e a r c hs u b j e c to n t h es o f t - d e c i s i o n d e c o d i n g o fb l o c kc o d e s i nt h i sp a p e r , w ea d o p tt h ec o n c e p t o f g e n e r a l i s e da r r a yc o d e s ( g a c s ) t o r e a l i z es i m p l et r e l l i sc o n s t r u c t i o n o fb l o c kc o d e sa n dt h et r e l l i sd e c o d i n gm e t h o ds i m i l a r t ov i t e r b i d e c o d i n g f o c u s i n go nt h e m o b i l ec h a n n e lw i t hs e r i o u sl o n g b u r s t e r r o r , w er e s e a r c ho n t h ep e r f o r m a n c eo fb l o c kc o d e sc o m b i n e dw i t h t h i s m a x i m u m 1 i k e l i h o o d d e c o d i n g m e t h o di n r a y t e i g hf a d i n g c h a n n e la n di t s a p p l i c a t i o n i n i m a g et r a n s m i s s i o ns y s t e m s r e s u l t s s h o wt h a ts o f t d e c i s i o nt r e l l i sd e c o d i n go fb 1 o c k c o d e s a d a p t s t o r a y l e i g hf a d i n gc h a n n e l w e l la n dv e r yg o o dt r a n s m i s s i o nq u a l i t yc a l l b eg u a r a n t e e dw i t hl o wt r a n s m i s s i o ns i g n a lp o w e r g a c ( 7 ，4 ，3 ) a n d c o d e ( 1 5 ，5 ，7 ) h a v eb e e nu s e df o re r r o r - c o n t r o li ni m a g e t r a n s m i s s i o n s y s t e m s o v e rr a y l e i g hf a d i n gc h a n n e li nt h i sp a p e r , a n db o t ho f t h e m b r i n g a b o u ts a t i s f y i n gp e r f o r m a n c ei m p r o v e m e n t t ot h es y s t e m t h et r a d i t i o n a le r r o r - c o n t r o l c o d i n gt e c h n i q u e s h a v ea g r e a t d i s a d v a n t a g e ，i e ，t h ec o n t r a d i c t i o no fr e l i a b i l i t ya n de f f i c i e n c y s i n c e e r r o r c o r r e c t i o n c a p a b i l i t y i so b t a i n e da tt h e e x p e n s e o f a d d i n g r e d u n d a n t b i t s ，s u c h a s y s t e m c o s tm o r e b a n d w i d t h o n l yb y c o m b i n i n gc o d i n g a n dm o d u l a t i o n ，c a nw es o l v et h ep r o b l e m t h e ni n t h et h i r dc h a p t e r , w es t u d yo nt h es i n g l el e v e lb c m s c h e m eb a s e do n g a c s i nt h i ss c h e m e ，ki n f o r m a t i o nb i t s a r ef i r s td i v i d e di n t on 。 b l o c k sw h i c hs a t i s f y i n g k = k + k l + k 2 + + k n 1 ，a n dk o k l ，k l = k 2 。2 k n 2 ，k n 1 2 0 t h e ne a c hb l o c ko fi n f o r m a t i o nd a t ai sm a p p e d t ot h ec o n s t e l l a t i o n o f m p s k ，w h e r e ，m = 2 如a n d e a c hs i g n a lh a st h ef o l l o w i n gf o r m s i = ( x o ，x 1 ，x k o - 1 ) ， t r e l l i sd e c o d i n gw i l lb ep e r f o r m e da f t e rd e m o d u l a t i o nt og e tt h e o r i g i n a li n f o r m a t i o nb i t s t h i sc m s c h e m eh a ss i m p l es t r u c t u r ea n di s e a s y t o r e a l i z e c o m p u t e r s i m u l a t i o ni sc a r r i e do u to v e ri d e a l l y - i n t e r l e a v e dr a y l e i g hf a d i n gc h a n n e lt o g e tp e r f o r m a n c ee v a l u a t i o n s a r i s f y i n gr e s u l t s a r e o b t a i n e d c o m p a r e dw i t hu n c o d e db p s ka n d 4 p s ks c h e m e s ，( 8 , 4 ：4 ) 4 p s k a n d ( 1 5 ，9 ，4 ) 8 p s ka c h i e v e ac o d i n g g a i n so f a b o u t2 5 d ba n d2 0 d b r e s p e c t i v e l y i na d d i t i o n ，i ti si n d i c a t e d b yf i 9 3 4a n df i g3 5t h a t ( 2 1 ，1 3 ，4 ) 8 p s ka n d ( 1 5 ，9 ，4 ) 8 p s kh a v e s i m i l a rp e r f o r m a n d e t h e nt h el a t t e ro n ei sm o r ea t t r a c t i v ef o ri th a s l o w e r c o m p l e x i t y s i n g l e l e v e lc ms c h e m eb a s e d o ng a c sh a ss h o w n g r e a t 柚 x2 舢 i i a d v a n t a g e f o ri t sa t t r a c t i v ep e r f o r m a n c e ，s i m p l es t r u c t u r ea n d e a s i n e s s t or e a l i z e b u tf u r t h e rr e s e a r c hm a k e st w o f a u l t so ft h i ss c h e m ec l e a r t ou s f i r s t ，t h i ss c h e m ed o e sn o tm a k ef u l l u s eo fs e t 。p a r t i t i o n t o o p t i m i z e t h ee u c l i d e a ns p a c e o n c eac o d ei sg i v e n ，t h ec o r r e s p o n d i n g m o d u l a t i o ns t y l ei sf i x e d s e c o n d ，t h i ss c h e m e h a sal o wt r a n s m i s s i o n r a t e ，e g ，( 12 ，7 ，4 ) 4 p s kh a sat r a n s m i s s i o nr a t eo f 1b i t s y m b 0 1 t h i s i sd u et ot h es t r u c t u r eo f g a c i n o r d e rt oo v e r c o m et h i sd i s a d v a n t a g e ， w er e s o r tt om u l t i l e v e lc o d i n gs y s t e m t h o u g hh u b e r e ta 1 p r o p o s e da i n f o r m a t i o nt h e o r e t i c a ld e s i g nr u l e - - - c a p a c i t yn l l e a sag u i d a n c et o s e l e c tc o m p o n e n tc o d e s ，w et h i n k t h i s r u 1 eh a s i t so w nl i m i t a t i o n f i r s t ， l t r e q u i r e st h ec a p a c i t yo f e a c he q u i v a l e n tc h a n n e lo fam l c s y s t e m ， w h i c hi sh a r dt og e ti ns o m ec a s e s s e c o n d ，b l o c kc o m p o n e n tc o d e s s e l e c t e du s u a l l yh a v el o n gc o d el e n g t hi no r d e rt om e e tt h ec o d er a t e r e q u i r e da n dt h u sd e c o d i n gc o m p l e x i t ya n dd e c o d i n gt i m ed e l a ya r e m c r e a s e di n e v i t a b l y m o r e o v e r , t h ec a p a c i t yr u l e a p p l i e s t om l c s y s t e mw i t hm s dd e c o d i n gm e t h o d b u tl o n gt i m ed e l a yo fm s d d i s c o u n t si t s a p p l i c a t i o n i nr e a l - t i m e c o m m u n i c a t i o n s o m e t i m e s ， p d li sp r e f e r r e d ，a n di nt h i sc a s e ，c a p a c i t yr u l ec a nn o tw o r k b e a r i n gt h e s ed i s a d v a n t a g e si nm i n d ，w et r yt of i n da ne f f i c i e n t b c ms c h e m ew i t hl o w e rc o m p l e x i t yf o rr a y l e i g hf a d i n g c h a n n e l s o m eo fo u rr e s e a r c hw o r ki sr e c o r d e di nc h a p t e r5a n dc h a p t e r6o f t h i s p a p e r f i r s t ，m u l t i l e v e l g a c p d l s y s t e m i s s t u d i e d b y c o m p a r i n g t h ec o n s t e l l a t i o na n dp e r f o r m a n c ed i f f e r e n c eo f u pa n db p , an e wd i s t a n c em e t r i co fm l c i sf o u n dw h i c hc o n s i d e rn o to n l yt h e d i s t a n c ea m o n gs y m b o l si nt h es a m es u b s e tb u tt h ed i s t a n c eo f s u b s e t a n ds u b s e t b a s e do nt h i sn e wd i s t a n c em e t r i c ，ar u l ef o rc o m p o n e n t c o d e ss e l e c t i o ni s p r o p o s e d s o m e t h r e el e v e lb c ms c h e m e sa r e c o n s t r u c t e da c c o r d i n gt ot h i sr u l ea n ds i m u l a t i o nr e s u l t sw eg e tc a n s e r v ea sag o o d p r o o f t ot h ep r o p o s e dn e wd i s t a n c ec r i t e r i o n an o v e ls t r u c t u r eo ft w o l e v e lc o d i n gc o m b i n e dw i t h8 p s ki s p r o p o s e di n t h i s p a p e r t o g e ti m p r o v e dp e r f o r m a n c ew i t h d e c r e a s e d s y s t e mc o m p l e x i t y c o m p a r e d w i t ht r a d i t i o n a l8 p s kt h r e el e v e l c o d i n g ，t h i ss t r u c t u r eh a st h ef o l l o w i n ga d v a n t a g e s f i r s t ，i tg r e a t l ys i m p l i f i e st h ec o d i n gc i r c u i t b e c a u s e o n l yt w o e n c o d e r sa r e r e q u i r e d s e c o n d ，d e c o d i n g t i m ed e l a yi ss h o r t e n e d t h i r d ，f o rt h e r ea r eo n l yt w os t a g e so fd e c o d i n g ，e r r o rp r o p a g a t i o n i sa l l e v i a t e d 0 摘要 m o r e o v e r , t h i ss t r u c t u r ec a np r o v i d ee n h a n c e de r r o rp r o t e c t i o nt o m o r ei n f o r m a t i o nb i t s t r a d e o f fb e t w e e nu e p p r o p e r t ya n do v e r a l lb e r p e r f o r m a n c eo f t h es y s t e mi sa l s oc o v e r e di nt h i sp a p e r av a r i e t yo fs c h e m e sa r e p r o v i d e df o rd i f f e r e n ts e r v i c e s c h a p t e r7g i v e sar o u g he s t i m a t i o no n t h eh a r d w a r ec o m p l e x i t yt or e a l i z et h ep r o p o s e ds y s t e ma n dt h i sw i l l h e l p t ot h e s es c h e m e s p r a c t i c a l k e y w o r d s ：g e n e r a l i z e da r r a yc o d e s ，t r e l l i sd e c o d i n g ，b l o c kc o d e d - m o d u l a t i o n ， m o b i l ef a d i i l gc h a n n e l ，d i s t a n c em e a s u r c 符号说明 广义蹦列码 最大似然译码 采用并行译码的多级编码系统 采用多阶段译码的多级编码系统 渐进编码增益 长为f l ，信息位为k ，最小汉明距离为d 的分组码 q 元伽罗华域 信号星座第i 次分割后符号间的最小平方欧氏距离 c7 和c “模2 相加 译码网格的深度 译码网格的状态数 q 函数( e r f 的补函数) 信噪比 信号星座中子集与子集的距离 误比特率 第，级分量码的误比特率 毗 缸 曲 佃 朋 k m p ， c d c c g ， ( 丑 r 。 灿 呲 眦 觚 沁洲 色 k k 虬 善| 屯即 前言 前言 日益增长的用户量和新的无线通信技术的不断涌现预示着移 动通信方兴未艾，蓬勃发展的同时也给它带来了前所未有的挑 战。业务量的增加使得频带资源越来越拥挤，邻道干扰，人为电 磁波噪声越来越严重，成为移动信道中除环境地形等造成的多径 衰落外又一大干扰因素 1 】。如何在日益恶化的通信环境中保证 通信质量，是人们不懈研究探讨的问题。同时未来的移动通信是 多种业务的综合，包括了话音，数据和图象等。为节省带宽，图 象在传输前要经压缩技术的处理，如m p e g 一4 。但是压缩后的图 象信息对噪声更加敏感。假定压缩比为10 0 0 ：1 ，那么压缩图象 中一比特的错误将使未压缩图象中10 0 0 比特受到影响 2 】。因而 在多媒体传输系统中，差错控制尤为重要。 不仅如此，移动通信综合业务的发展也对不等错误保护度提 出了要求。不同的通信业务有不同的保真度要求，如，语音电话 需要1 0 。2 10 叫的误比特率；而语音带宽的数据传输及e m a i i 和传真则要求1 0 “；电视电话的误比特率要求达到1 0 。【3 】。如 果对所有的业务都采用1 0 一作为标准显然不能满足要求，如果都 要求达到1 0 - t j 则实为一种浪费不同业务如此，同种业务中的 数据也有重要和不重要的分别。如果能区分对待，必将节省带宽， r a y l e i g h 信道中分靠j 码的嘲格洋码成坌垫堕堕塑型塑塑堑 提高有效性。因而，不等错误保护度是对编码调制一个基本要求。 除此之外，我们还期望编码调制方案有短时延的特点。否则，它 在实时语音通信中的应用将大打折扣即使它能提供优良的误比特 性能。 分组码和卷积码是有噪信道中数字传输系统中使用的两种主 。 要的差错控制技术【4 。虽然分组码的发现要早于卷积码，但网格 译码或维特比译码这种我们熟知的最大似然译码方法却首先应用 与卷积码中【5 ，并取得了巨大进展，在多种通信系统中发挥作 用。而分组码由于有一定的数学结构，一般采用代数译码。其优 点是有一些通用算法，可以简洁、迅速的实现；不足之处在于难以 采用软判决，影响了其性能的改善。研究表明，在a w g n 信道中， 软判决译码方案要比硬判决多获得2 d b 的增益，而在r a y l e i g h 衰 落信道中，这种额外编码增益还要更大一些【6 。因此，近年来， 分组码的最大似然译码引起了人们的极大兴趣，而网格译码更是 一个突出的研究热点。在最小网格，网格的限及复杂度等方面的 研究取得很大进展 7 1 0 ，但主要侧重于理论方面，至于这项技 术在现有通信和信息系统特别是移动个人通信系统中的应用，仍 然有待研究 传统差错控制编码是靠加入冗余位，因而纠错能力是以牺牲 前言 信道带宽为代价的。为了增加带宽有效性，就产生了编码调制相 结合的方案：b c m 与t c m 。b c m 虽然有时延小、错误传播少的优 势，但由于缺少高效的编码器和译码器，其发展一直滞后于 t c m i i 】，目前的研究多局限在a w g n 信道中。但由于信道特征的 巨大差异，在a w g n 中成立的结论往往不适合于移动信道所以， a w g n 中的编码调制方案也不能在移动信道中生搬硬套。移动信道 应该有与之相匹配的编码调制方案。低复杂度的分组码的网格译 码的实现将有助于b c m 的发展，有助于移动信道中最优c m 方案 的实现。 多级编码系统由于其内在的不等错误保护特性及频带和功率 有效性一直受到人们的热切关注。从i m a i 的论文发表以来，在 这方面又有大量的论著。编码调制的核心是优化编码的欧氏空 间，而不是象传统编码那样增加它们的汉明距离，因而系统的带 宽有效性得到了保证。对于考虑了边界效应的实际编码调制系 统，h u b e r 等人证明如果分量码选取合适，用多级编码系统和多 阶段译码的结合可以达到调制方案的容量【1 2 】计算机模拟结果 也显示应用信息理论的设计准则，多级编码系统可以达到逼近山 农限的功率和带宽有效性【12 】但是l u b e r 提出的设计准则有 其自身的局限性首先，它要求知道多级编码系统各等价信道的 ! 翌型塑笪望! 坌丝型竺鬯垡堡堡垒坌望堡塑塑型竺竺窒 信道容量，这在有些情况下是很难得到的。例如，r a y l e i g h 信道 中采用8p s k 调制时各等价信道的容量仍是未知的其次，为了 应用信道容量规则，作为分量码的分组码需要有很长的码长以满 。 足对码率的要求，这一点不可避免地导致译码复杂度和译码延时 的增加。而且，h u b e r 的信道容量规则仅仅适用于采用多阶段译 。 码的多级编码系统。但多阶段译码中复杂度高及时延长的不利因 素使得它很难在实时通信中发挥作用。因而，我们有时会倾向于 各级的并行译码( p d l ) ，这时，信道容量规则将不再适用。本文 正是针对这些缺陷，寻求r a y l e i 曲信道中低复杂度的有效的编 码调制方案，寻找到一种多级编码系统中新的距离度量，并由此 提出适用于m l c p d l 的分量码选取准则。综合考虑误比特性能及 译码复杂度的情况下，研究了不同的译码方法在多级编码系统中 的应用，提出了一种新的两级编码采用8 p s k 调制的方案。与传 统三级编码8 p s k 结构相比，这种方法复杂度大大降低，时延大 大缩短，同时又能保证很好的误比特性能，可望在未来移动通信 系统中发挥巨大作用。另外本文还致力于研究不等错误保护特性 与系统整体性能的折衷，针对不同的通信业务，给出多种方案以 满足对不等错误保护与系统整体性能的要求。 本文的第一章研究了分组码网格译码在r a y l e i g h 衰落信道 前言 中的性能，及其在图象传输系统中的应用。第二章致力于单级编 码调制方案的性能分析和模拟。对于多级编码调制方案的特性在 第三章进行探讨第四章致力于寻找低复杂度的多级分组编码调 制方案。一种新的距离度量将在此提出并用于指导分量码的选取 以获得更好的性能。为了进一步降低系统的复杂度，同时还提出 了一种新的编码调制方案，将两级编码与8 p s k 结合。此方案在 大大降低时延和复杂度的情况下保证了很好的误比特性能。论文 的第五章是研究工作的结论和展望。 ! ! ：! ! 尘! 笪丝! 坌型型竺鬯竺堡竺墨坌型塑型! 塑丝塑竺翌一 第一章分组码网格译码在r a y ieig h 衰落信道中的性能 只要信息传输率r 不大于信道容量c ，则存在一种编码，当码 长n 足够长时，它可以使信道输出端的误比特率任意小，而信息传 输率仍可以无限的接近信道容量【13 1 4 】。这就是著名的有噪信 道编码定理，或山农第二定理，它开创了纠错码这一研究领域。 。 分组码以其简洁的数学结构在数字传输系统中表现出旺盛的 生命力。一般的代数分组码定义在符号域g f ( q ) 上，以汉明距离 ( h a 咖i n gd is t a n c e ) 为度量，针对q 或二进制对称信道，采用硬 判决限定距离的代数译码方法，如b e r le k a m p m a s s e y 算法等。 这种硬判决代数译码容易实现却影响了码纠错能力的充分发挥。 正由于这个原因，近年来分组码的软判决译码引起了人们浓厚兴 趣 1 5 - 18 。 1 1 分组码的软判决译码 对于( n ，k ，d ) 的线性分组码，要实现最佳的最大后验概率 译码( m a p ) 或最大似然译码( m l d ) ，其计算复杂度为0 ( 2 2 ) = 0 ( 2 加) 或 0 ( 2 ”。) = o ( 2 州卜) 。当n 或k 很大时，工程上很难实现。因此人们 一 努力寻找接近m a p 或m l d 性能的次最佳或准最佳译码。这其中包 括逐位软判决译码和逐组软判决译码。在逐位软判决译码算法 中，特别值得提出戢是由b a h l 等人提出的b c j r 算法 1 9 】。它使 第一章分组玛网格译码在r a y l e i g h 衰落信道中的性能 用迭代方法计算每位码元的最大后验概率，适用于任何线性分组 码和卷积码，由于计算每位码元的最大后验概率时采用了迭代， 因此计算速度很快。在1 9 9 3 年t u r b oc o d e s 提出后，这种算法 引起了人们的广泛注意。逐组软判决译码的系统研究开始于 f o r n e y 的博士论文中提出的广义最小距离译码( g m d ) ，g m d 译码 是一种迭代纠错译码，算法需要d 2 次硬译码，得到d 2 个候选 码字，然后挑出一个最好的作为译码器的输出。c h a s e 在g m d 基 础上提出了c h a s e 算法。这是一种伴随式译码，利用可信信息寻 找最可能的错误图样，根据试探错误图样数目的不同又可分为 c h a s e l ，2 和3 【2 0 】。分组码逐组软判决译码的另一个重要研究方 向是网格译码，目前已成为研究热点。 分组码的网格图表示是在1 9 7 4 年由b a h l 首次提出的1 9 7 8 年，w o l fj 指出，定义在g f ( q ) 上的任意( n ，k ，d )线性分组 码均可用网格图表示，并采用v it e r b i 译码算法【2 1 】w o l f 还为 所有乘积码找到了最小网格，但是，他提出的网格构造方法非常 复杂，需要很大的计算量而且网格的分支仅仅以编好的码字标 识，译码后若要恢复原始信息，需要额外的操作，这就更加大了 运算量，因而，实际上这种译码方法是不实用的。1 9 8 8 年，f o r n e y ， 从陪集码的角度构造出网格网格中的每条分支可表示几个字 r a y l e i g h 仁遒中分 i i 码的嘲村坦蔓塑垄坌丝堡型塑型塑竺茎 符，并且这种网格图具有结构化的特征，从而简化了v i t e r b i 译 码算法的实现【7 。如果n 可以被h 整除，则利用码的结构特征 由n 段结构构造n k 段网格图是可能的，如r m 码和o o l a y 码。 f o r n e y 利用陪集表示的四段网格图的表示如下： 设s 是m 个子集t ；的并，1 ，m ，则二次结构为 。 u = 1 s ，丁1 2 = 1 ( s 1 ，5 ：) ，s ，s ：t ，i = 1 , 2 ，m 其对应的网格图由两段组成，中间端边界上的状态数为i s i t i ， 由ls t iz 的定义和网格结构很容易给出两层二次结构，即四次结 构 i s i t i v i 2 垒l l s r 1 2i i t i v l 2 。2 四次结构对应的网格图由4 段组成，最坏分支的复杂性为m n 2 ，最 坏译码复杂性为4 m n 2 - 1 ，其中m = ls t i ，n = i t i v i ，适当选取矩阵， 由四次结构即可构造r m 码的网格图。 f o r n e y 等人提出的网格构造方法只对某些特殊的码找到了对 应的最小网格图，而对于绝大多数码尚不清楚其最小网格图指标 s ( c ) 和最小网格图的结构。此后，m u d e r ，推广了f o r n e y 的方法， 一 给出任意线性分组码网格中状态数的下限，指出网格大小与码的 其它参数存在一个折中 8 】，但只为一些特殊的码找到优化组合 方案，仍然没有对所有分组码通用的解决方法。直到1 9 9 3 年 第一章分组码网格译码在r a y l e i g h 衰落信道中的性能 b h o n a r y 提出了广义阵列码的概念【2 2 】，并给出了在此基础上的 网格构造方案此方法能够以更低的复杂度实现最小网格，并且 几乎适用所有的分组码，因而对它的研究将有很大的现实意义。 实际上这是一种基于s h a n n o n 乘积的最小网格设计。一些码的代 数结构决定了它们可以由一些“小”的线性码构成，如果已知这 些小线性码的网格结构，则有可能由此构造给定码的最小网格结 构 23 】设t ，t 是两个n + l 层网格图，第t 层的状态分别为 s j “，印，i = l ，n ，f = l ，费，网格图的每条分支代表h 个字符，则t 与 t 的s h a n n o n 乘积t xt ，也具有n + l 层，第t 层的状态由i s ：，j ：】表示， i = l ，n ，_ ，= 1 ，对，当且仅当t 中有一条连接s j ”1 和sc i ) 的分支 6 【s j “，s j 】，t 7 中有一条连接雪j ”和$ 的分支6 心j “”，影】时，t t 7 中 有一条连接【s j ”，雪：”1 ，】和f ：，j ：】的分支，该分支的标号为 【s j “”，s ：】+ 【雪j “”，毒：】，其中的加法为卵中的矢量加法， 一 g 。”，_ 】和【窝“”，影】分别为分支b s ：t - 1 ) , s ：】和6 每”“，影】的标 号本文的网格译码主要基于这种网格译码 - 1 2 广义阵列码的构造 1 2 1 阵列码与广义阵列码 b h o n r y 提出的广义阵列码是阵列码的扩展阵列码( a r r a y c o d e s ) 通过组合两维或多维子码构造而成，子码一般结构简单， 容易实现。乘积码，级连码都属阵列码，而行列码( r o w a n d c 0 1 u m nc o d e ) 却是其中最简单的一种。其结构如下： x i ij 1 2 x 2 1x l 鼬r 2 lo 2 2 p 2 1p _ 船 o uj 地p l n z z 2j z 2 t lp ： j t 2 ，o h ip k z , , p 2 ，p 一p h l 其中乃和p i j 分别汞示信息位和校验位。显然，若行码和列码分 别为( n l ，k l ，2 ) 和( n 2 ，k 2 ，2 ) 单校验码，则组成的阵列码( n ，k ，d m l n ) 满足n = n 1 n 2 ；k = k l t k 2 ；d m 。= d 1 + d 2 = 4 。例如，可以设计一个 ( 4 ，3 ) ( 4 ，3 ) 的行列码如下： 工2工，p l 屯工6p 2 o sx 9p 3 p 6p 1p i 由于行码与列码结构简单，其生成矩阵一般很明显，而阵列 码的生成矩阵g 只需将行码与列码的生成矩阵g 和g 。进行 k r o n e c k e r 乘法即可得到【3 6 。由此可见，阵列码的设计非常简 单，但由上例也可看出一个缺陷，即对于码长n = 1 6 和d 咖；4 ，信 息位k 最大只能取9 。但是对于n = 1 6 和d 咖= 4 ，信息位k = l l 的 线性码也是存在的 3 6 。怎样使得对于一个给定的码长和最小距 离可以容纳更多的信息位，从而得到更高的码率呢? 这就需要广 义阵列码( g a c ) 。下面构造过程便可看出广义阵列码的含义 一南风 j j 496 c 第一章分组码网格译码在r a y l e i g h 衰落信道中的性能 假设要构造的码字为( n 。，k 。，d 。) ，则步骤如下 3 5 ： ( 1 ) 若n o 是质数，令n = n o + 1 ，否则n = n o ； ( 2 ) 构造n = n l n 2 的基本乘积码c 1 ，c l 由单校验列码( n 2 ，k 2 ) 和行码r i = ( n l ，k l ，d 1 ) 组成，如图1 1 ( a ) 所示，其中d 1 等于 - 对d 0 2 取整。 ( 3 ) 设计附加乘积码c 2 ，如图1 1 ( b ) 所示。其中p 为k l 列n 2 l ：r a ( a ) 基本乘积码e l( b ) 附加乘积码c 2 图1 1g a c 的构造 行的零矩阵，而a 的第一行含k = n l - k 1 个信息位，每一列又均 为( n 2 ，1 ，n 2 ) 的重复码。 ( 4 ) 如果信息位的个数还不满足要求，需要再加一位信息位， 就要设计附加码c 3 ，如图1 1 ( c ) 。其中0 表示( n 2 - 1 ) 行n 1 列的零矩阵，b 是( n l ，1 ，n 1 ) 的行码。 ( 5 ) 将c l ，c 2 ，c 3 的对应位进行模2 加操作，便得到广义阵列 码c ( 6 ) 如果第一步中令n = n 。+ 1 ，则这时需删除最后一个符号，得到 所需的( n o ，k o ，d 。) 码字。 例如，选择c 1 ，c 2 如下，便可得到一个( 8 ，4 ，4 ，) 分组码c ，而 乞i千陋l 耷l引j 通过删除c 的最后一个符号，便可得h a m m i n g 码( 7 ，4 ，3 ) 。 x 1 x 4 + p 1 工2 x 4 + p 2 工3 工4 + p 3 p 4x 4 + p 4 1 2 2 分组码的递9 - 3 编码 广义阵列码的概念可用来构造许多线性分组码，但构造中的 关键是选取合适的阵列大小和相应的分量乘积码。这个i = - 1 题目前 仍未解决，但对一些特别的线性分组码如r e e d - m u l e r 码和 h a m m i n g 码却已有一定的方法 3 7 3 8 】，这就是递归编码。r m 码的 递归编码基于以下定理及其推论： a ( r 一1 ，m 一1 )a ( r ，m 一1 ) 入-