（通信与信息系统专业论文）reedsolomon码代数软判决译码研究及其在磁记录信道中的应用.pdf

重庆邮电大学硕士论文 摘要 摘要 r e e d - s o l o m o n ( r s ) 码是非二进制b c h 码的最重要、最常用的子类，具有纠随 机符号错误和随机突发差错的优越性能。因此，其在深空通信、数字音频、视频 传输以及高密度磁记录设备等领域均具有广泛的应用。近年来，随着信息的膨胀 人们对大容量磁盘存储系统的需求急剧增加，研究者们正努力寻找既满足高存储 密度要求又具备极低误码率性能的信号处理方式。实现磁记录信道下r s 码的低复 杂度的软判决译码也成为许多研究者所追求的目标，而运算复杂度过高是r s 码的 软判决译码算法发展的瓶颈。但是，随着近年来重编码与坐标转换技术的发现与 应用，基于插值的代数软判决译码算法的复杂度得到了极大地降低。鉴于此，本 文在利用这些技术的基础上提出一种基于混合多项式选择与因式分解的低复杂度 c h a s e 型代数软判决译码算法，并实现其在磁记录信道下的应用。 本文提出的代数软判决译码算法是基于采用重编码与坐标转换技术后的插值 二元多项式及有效的译码信息多项式特征，对代数软判决译码算法进行的改进研 究。该算法首先构造出有2 n ( r l “。2 的码字均包含在以z 为变量的因式里。但是 s u d a n 的这一算法复杂度随着译码半径t 的增加而急剧增加，与传统的硬判决算法 相比，要付出更多的运算复杂度代价。 2 0 0 0 年，k o e t t e r 和v a r d y 深入推进了s u d a n 的工作，提出了一种实用的代数 重庆邮电大学硕士论文 第一章绪论 软判决算法，即我们所熟知的k v 算法【l2 1 。在s u d a n 算法的基础上，他们利用信 道输出的对数似然信息构建出更加有效的q ( x ，z ) 。这一算法只需按候选位置所分 配的信度进行插值，打破了s u d a n 算法迫使q ( x ，z ) 必须以相同的信度穿过每一个 接收值的限制。因此，这一算法相对s u d a n 算法而言有效的降低了运算复杂度， 且在性能上比硬判决算法有明显的改善。从此，越来越多的研究工作集中到了r s 码的软判决译码上。但是软判决译码算法在性能上获得的改善，却要付出巨大的 复杂度代价。许多学者为降低软判决译码算法的复杂度进行了广泛的研究，相对 硬判决算法的复杂度而言，仍然有较大的差距。 近年来出现的另外两种实用的代数软判决译码算法是：b g m d 算法【1 3 】和l c c 算法i l4 1 。尽管它们采取不同的多样性分配方式，但是具有两个相同的关键步骤： 多项式插值与因式分解。而多项式插值与因式分解过程的运算复杂度偏高是制约 代数软判决译码算法发展的瓶颈。加之r s 码始终缺乏十分简单有效的译码算法， 并且在a w g n 信道下，r s 码的译码性能远不如卷积码，更不用说译码性能接近 香农限的t u r b o 码【1 5 】和l d p c 码【1 6 ，1 7 1 。更令人惊讶的是，g u r u s w a m i 和v a r d y 证明了r s 码的最大似然译码是一个n p h a r d 问题【1 8 】。r s 码的发展历程尽显曲 折，但是r s 码本身却具有严谨的代数结构，仍然有着广泛的应用。通过理论分析， 人们可以看到r s 码的软判决译码依然有着巨大的潜力，也许它将不逊于任何纠错 码。因此，越来越多的研究者开始为它设计简单有效的软判决译码算法，致力于 挖掘它的潜力，以期获得更大的系统增益。例如：为了最大限度的降低代数软判 决译码算法的复杂度，g r o s s 等人提出了降低插值复杂度的重编码方法 圳( r e - e n c o d i n g ) ；k o e t t e r 等人给出了提取公共插值因式以降低插值运算复杂度的坐 标转换方法1 2 0 ( c o o r d i n a t et r a n s f o r m a t i o n ) 。b e l l o r a d o 与k a v c i c 将重编码技术与c h a s e 算法进行结合，提出了低复杂度的c h a s e 型译码算法【1 4 2 1 1 。另外，利用a s d 算法 的代数结构特征，能够将插值和因式分解过程进一步简化。j z h u 等人给出了进一 步的简化插值方式，并使用类似于c h i e n 搜索和f o m e y 算法的方法替代因式分解， 使得运算复杂度进一步降低1 2 2 , 2 3 】。 1 2 r s 码的c h a s e 型译码算法简介 在介绍c h a s e 型译码算法之前，有必要介绍广义最小距离( g e n e r a l i z e d m i n i m u md i s t a n c e ，g m d ) 译码算法2 4 1 。它是f o m e y 于1 9 6 6 年提出的基于接收序列 的l r p ( l e a s tr e l i a b i l i t yp o s i t i o n ) 处理的译码算法。g m d 算法不但适用于二进制码， 而且也适用于非二进制码f 2 5 】。它是一种简单、优雅的译码算法，利用接收符号的 2 重庆邮电大学硕士论文 第一章绪论 可靠性信息来提高代数译码性能。对于最小汉明距离为的( n ，k ) 线性分组码， g m d 算法基于错误删除代数译码方法产生最多( d f n i n + 1 ) 2 个候选码字，并从其中 选择最有可能的一个作为译码结果。 为了推广g m d 译码方法，c h a s e 在1 9 7 2 年发明了三种算法【2 6 。，也即c h a s e 算法一1 、c h a s e 算法2 、c h a s e 算法3 。其中，c h a s e 算法3 用取补操作替代了g m d 算法中对硬判决接收序列的l r p 组的删除操作。因此，对于译二进制线性分组码， 这两种算法非常类似。c h a s e 型译码器将满足最大后验概率的译码码字作为正确码 字输出。因此，正确的译码方法能够提供准确译码测试集中的任何矢量的译码过 程。对于传统的硬判决算法，c h a s e 所提出的这种译码结构能够提升任意码型的硬 判决译码性能。当然，c h a s e 型算法与传统硬判决算法的主要差别还在于前者利用 可靠信息构造硬判决矢量测试集( t e s t s e 0 ，并将测试集中的每一个硬判决矢量独立 的应用到译码算法中，而后者则直接将从信道接收的唯一m a p ( m a x i m u m a - p o s t e r i o r ip r o b a b i l i t y ) 硬判决矢量作为译码算法的输入。很显然，c h a s e 算法的这 一改变要增加运算复杂度。通常情况下，c h a s e 型算法考虑可靠度最低的t 1 个候选 位置并将每个位置上的所有可能取值符号进行组合，这些在某个位置上有差异的 矢量便构成测试集。性能的提升自然会随着测试集的基数( t e s t s e tc a r d i n a l i t y ) 增长。 换句话说，算法复杂度将随着t 1 的增长呈现指数增长。 需要说明的是，对于译码半径为t 的算法，c h a s e 型译码算法蕴含纠正啪个 硬判决错误的能力，但是不能确信在每一次纠正超过t 个硬判决错误时都能够获得 成功。因此，c h a s e 型译码算法使现有算法的译码半径得到了一种虚假延伸 ( p s e u d o e x t e n s i o n ) 2 1 1 。对编码长度为n 、有效信息长度为k 的r s 码，传统的硬判 决算法能够正确纠正双n k + 1 ) 2 个硬判决错误。并且在给定q 的情况下，c h a s e 型的这一构造对于高码率的较长码而言，能够获得比低码率的较短码更好的性能 表现。因此，对于( n k ) 较大的r s 码型来说，性能的提升需要大幅增加t 1 的取值， 而这样做的直接后果是要付出复杂度增加远大于性能增益的代价。 1 3 论文研究内容、目的及意义 本文的主要研究内容可以分成两个部分： 首先是针对r s 码的软判决译码算法展开的研究。目的在于提出改进的软判决 译码算法，并在保持较低译码运算复杂度的同时，取得性能上的增益。 其次是实现改进算法在磁记录信道下的应用。并对磁记录信道采取合理的检 测方法，促使磁记录信道以简单有效的方式实现与改进的r s 码译码算法的级联。 3 重庆邮电大学硕士论文第一章绪论 近年来，t u r b o 码和l d p c 码是众多研究者所追踪的热点研究对象。这两类 逼近香农限的码型的出现，使得无法提供简单有效的软判决译码算法的r s 码遭遇 “冷落。但是随着对l d p c 码研究的深入，人们发现它并没有代数的、系统的构 造方法【1 1 ，尽管近年研究者提出的准循环l d p c 码和原模图l d p c 码编码复杂度较 低，但由于很难找到其最小距离从而根据最小距离去分析其在极低b e r ( 是具有最小( 1 ，k - 1 ) 权重、且满足( 2 2 1 ) 约束的二元多项式，因此必有： d e g ( 1 k q ) ( q ( x ，z ) ) 嬖三 ( 2 2 5 ) 将z = f ( x ) 带, k - 元多项式q ( x ，z ) ，可以得出一元多项式h ，由下式给出： h ) 2 q ( x ，f ( x ) )( 2 2 6 ) 因此，vf e ，必有下式成立： h ( q ) = q ( q ，厂( ) ) = q ( q ，q ) = q ( q ，j l i ) = 0( 2 2 7 ) 既然h o ) 在吲个候选位置上存在根，因此必有下列一个结论成立： ( a ) d e g ( h ( x ) ) 爿e i = ( n 0 ( b )h 0 ) = o 利用q ，z ) 的表达式将h 进行扩展，有： h ( z ) = q u 一【( z ) 】 ( 2 2 8 ) 由信息多项式厂o ) 的定义可知，d e g ( f ( x ) ) ( k 一1 ) ) ，因此： d e g ( h ( z ) ) d e g ( 1 k _ 1 ) ( q ( 舻) ) 旦警 ( 2 2 9 ) 假定l 为，由于( 刍n + - k - 2 ，则有下列不等式成立： 掣( n f ) d e g ( h ( x ) ) 半 ( 2 3 0 ) 上式明显不成立，因此假设h o ) 两是错误的。既然h = 0 ，那么z = f ( x ) 必是二元 多项式q ( x ，z ) 的根，即z - 厂 ) ) lq # ) 。推论1 即得到证明。 由于q ( x ，z ) 的( 1 ，k - 1 ) - 权重上限为： d e g ( 1 k - 1 ) ( q ( x ，z ) ) n + _ k - 2 ( 2 31 ) 如果q ( x ，z ) 的多项9 “x i z 7 存在且g 0 。那么，下列不等式必然成立： d e g ( 1 k - - 1 ( q ( x ，z ) ) j ( k - 1 ) ( 2 3 2 ) 当j - - 1 时，不等式( 2 3 1 ) 和( 2 3 2 ) 都成立；当趁时，则不等式( 2 31 ) 和( 2 3 2 ) 不可能 都成立，因此只能取户l 。即满足推论1 条件的q ，z ) ，z 变量的最高指数为1 。 1 3 重庆邮电大学硕士论文第二章低复杂度c h a s e 型软判决译码算法的构造原理 推论2 证毕。 2 3 1 单一测试向量的逐点插值 单一测试向量的逐点插值方式是实现整体测试向量集插值的基础，文献u 8 给 出了完成逐点插值的算法。这一插值算法通常被称为尼尔森算法【3 1 ( n i e l s e n s a l g o r i t h m ) ，而尼尔森算法是在文献 3 2 提出的代数插值算法的基础上得到的改进 算法。该算法在对矢量y i 嘲，o 批l7 ，枷17 ) 进行插值时将独立考虑各个候选插值 位置。若将 0 ，1 ， n 1 ) 中的任意m 个候选位置点记为集合p 。互 0 ，l ，n 1 ) ，则在 完成第m 次插值算法后，构造出来的中间二元多项式可表示为q f 丑( x ，z ) 。并且它 满足下述约束情况： q m ( q ，咒，) = 0 ，v j ep ( 2 3 3 ) 在完成第n 步插值后， 扔 ( a o 纠v i , o ) ，( 5 1 ，耽17 ) ，( l ，y i , n - 17 ) 均是多项式 q 。( 工，z ) 的根，因此： q ( x ，z ) = q ( x ，z )( 2 3 4 ) 这里需要特别说明的是，在插值过程中可以忽略候选插值点的顺序。因此，可以 按照任意的顺序对候选位置点进行插值。 算法l 对单一测试向量的逐点插值 具体算法流程 第一步，输入测试矢量：y 7 = 执7 , y l7 ，, y n 1 ，) 第二步，初始化多项式集合：g = g o 声) ，g l g ，z ) ) = 1 声) ； 第三步，循环插值： f o r i = 0t o ( n 一1 ) 多项式选择： a x e ) = a r g 峨，z ) e g d e g o k - 1 ) ( g ( x , z ) ) ，g ( a i , y i ) 目) ) g 声) = g b 力) 多项式更新： 鲥舻 = g o 力hg o 力f i x , z ) ) a x e ) = ( 什0 【f ) 撖声) g = g o z ) ，g l 力) = g z ) 以z ) ) e n d f o r 第四步，输出：q ( x , z ) = a r gm i i 坼# ) gd e g o ，k - 1 ) ( g ( x , z ) ) 1 4 重庆邮电大学硕士论文第二章低复杂度c h a s e 型软判决译码算法的构造原理 算法l 给出了无需考虑插值点顺序的插值算法，在该算法的插值过程中将产 生最d x ( 1 ，k 1 ) 权重的二元多项式q ( x ，z ) 。文献【3 1 给出了算法1 能够产生具有最小 ( 1 , k - 1 ) 权重的二元多项式的证明。对于o 力 ( a o 。v o ) ，( a l l y l ) ，( h y n 1 ) ) ，该二元 多项式q ，z ) = o 。 2 3 2 对多项式集g 的修改 对于一个给定的测试向量y 7 ，算法1 能够构造出所需的二元多项式q ( x ，z ) 。 但是对于稍长的r s 码，按照算法l 的方法对测试向量集中的所有测试向量进行逐 点插值，插值过程所需要的乘法运算将是数以万计的。因此，复杂度偏高影响了 译码效率，并且使得硬件实现十分困难。前文对测试向量集的修改，使得所有测 试向量在r 所对应的候选位置上的值均为0 。利用这一特征对所修改的测试向量进 行插值将会极大的降低插值复杂度。文献 2 1 】对插值过程进行了深入的研究，提出 了二叉树插值的方法，而该插值算法正好能够与本文所提出的m s f 方法进行有效 的契合。在本章接下来的内容中，将深入透彻的分析这一插值算法。 为了降低插值过程的复杂度，先利用算法1 对r 所对应的k 个候选位置点进 行插值。并且使多项式集合g = - g o ( x , z ) ，9 1 ) 的初始化值为 l 芦) 。插值开始后， 在多项式选择的过程中先挑选出多项式a x , z ) 。由于r 所对应的每一个候选位置点 的取值都具有( 仅，0 ) 的形式且g l ( a i ，o ) = o ，所以必须选择u 力= g o ( x , z ) = l 。因此，多 项式集也应做相应的修改。在完成插值的初始化步骤时，应使得g 为下述形式： g = + 嘭) ，z )( 2 3 5 ) 按照相同的方式对r 所对应的候选位置点进行插值，在完成| r | 步插值后，多项式 集合具有如下形式： g = 、，( x ) ，z )( 2 3 6 ) 其中： v ( x ) = 1 - i ( x + 嘭) ( 2 3 7 ) i e 矗 在这里，将毗) 记为倍乘因子。从g 中的多项式中提取出倍乘因子，可表示成如 下形式： g = v ( 工) 1 ， ( 2 3 8 ) v 【z j 从算法的多项式更新步骤中可以发现，在插值过程中v 将始终保持在每一步的二 元多项式中。因此，为了避免对v g ) 的重复运算、简化g 中多项式形式，在插值 前将g 中多项式均除以v ，并将除后的多项式集记为g ，表示如下： g = 1 ， ( 2 3 9 ) 1 5 重庆邮电大学硕士论文第二章低复杂度c h a s e 型软判决译码算法的构造原理 但是g 7 中二元多项式形式造成插值上的困难，在这里做变量替换，使z = z v 。 因此，变量替换后，g 简化成如下形式： g 7 = 1 ，z )( 2 4 0 ) 利用二元多项式集合g7 ，在接下来对剩余的( n k ) 个候选位置进行插值时，使用插 值变量点似g ) 。考虑到对z 进行替换时所作的修改，插值点的值也做相应修改： ( q ，只。) 一( q ，志( 2 4 1 ) 另外，( 1 , k 1 ) 一权重的计算也需作出调整。由于x i z j 可等价的表示成z 7 v 7 ( 曲，因 此0 力的( 1 ，k 1 ) 权重可以由下式得出： i _ ， d e g ( i , k - , 铬) = m a x d e g ( x v j ( 石) ) + ( k - 1 ) m a xd e g ( z j ) = i - j k + ( k - 1 ) 歹= f j ( 2 4 2 ) 从权重的定义知，可将调整后的权重视为该单项式的( 1 ，1 ) 权重。因此，可以修改 对 ，z ) 的插值过程，构造出满足最小( 1 ，一1 ) 权重的多项式。然后，重新替换变量z 后得到的多项式即等价于对0 ，z ) 插值后得到满足最小( 1 ，1 ) 权重的多项式。 从前文给出的插值方法可以知道插值多项式q ( x ，z ) 是从矢量y i 获取来的，并 且一元多项式v 的构造仅依赖于r 中的候选位置，而非这些位置上的具体取值。 因此在进行插值前，可以按式( 2 3 7 ) 直接构造出v 而无需对这些候选位置进行插 值。对整体测试向量集的插值只需在良所对应的( n k ) 个候选位置点上进行。通过 前面所述的变量替换方法，在插值过程中可以省去对v 的重复运算。由于v 的重度为k ，经过变量替换后插值步骤的运算复杂度将得到极大降低，对于高码率 的r s 码尤为突出。 2 3 3 测试向量集的联合插值算法 上节就多项式集g 的简化问题进行了讨论，并给出了简化方法。因此，插值 过程的运算复杂度得到了很大程度的降低。这些都得益于2 2 节中对测试集向量的 修改。然而，完成插值过程仍然需要对测试集中的每一向量单独进行插值。由( 2 1 1 ) 所示的测试集构造方式可知，测试向量之间有如下特性：每一测试向量在7 所对应 的n t 1 个位置上取值均相等，且任两向量之间只有一个位置点的取值不同。考虑到 测试向量的这一特性，本节将进一步讨论对所有测试矢量采用同一方式进行插值 的算法。 首先对7 对应的n - t 1 个候选位置插值，构造出满足最d x ( 1 ，k - 1 ) 权重的多项式 q ( m - t ) “z ) ，且v ( i j 3 e 1 , 2 ，2 q ) x 7 ，有： 1 6 重庆邮电大学硕士论文第二章低复杂度c h a s e 型软判决译码算法的构造原理 q 佃叫( 口，只。j ) = 0 ( 2 4 3 ) 在2 2 节中讨论了无需对r 所对应的k 个候选位置进行插值而直接构造v 的方法。 因此，利用( 2 3 7 ) 给出的公式构造倍乘因子v 也是扩展后的多项式集g = q l ( x a ) ， q 2 g 力，q 2 一g 力) 的倍乘因子。在接下来的过程中，只要对瓦所对应的n - k 个候 选位置进行插值。将茛对应的候选位置再次划分成集合b 。和b u ，并采用不同的方 法对b 。和b u 的候选位置进行插值。这里将b 。称为普通元集合，将b u 称为非普通 元集合。候选位置的具体划分方法请参见2 1 节内容，在此不再多加赘述。 首先考虑具有( n - k - n ) 个候选位置点的集合b 。由于b 。中的元素也是7 的元素， 因此测试矢量在b 。所对应候选位置上的取值均相等，有如下形式： 只，。= 沙，+ y ，叩 ( 2 4 4 ) 接着利用前文给出的算法1 对这些候选位置进行插值，构造出两个满足( 2 4 3 ) 的多 项式，并将它们记入集合g 。需要注意的是，这里构造出的多项式是利用z = z v 进行变量替换后得到的，因此它的根具有如( 2 4 1 ) 所示的形式。 结合上述讨论，将算法l 进行适当修改后应用于b 。所对应候选位置的插值过 程。构造集合g 。的具体方法如算法2 所示。 讨论到此，整个插值过程仅剩下集合b 。所对应的t 1 个候选位置点尚未完成插 值运算。下文将继续延续插值内容，针对集合b u 所对应候选位置的插值进行讨论。 虽然测试矢量在这1 1 个候选位置上的取值不相同，但是它们仅具有如下两种 形式： 只，= + 乃或只= + 乃2 肋 ( 2 4 5 ) 因此，在计算插值多项式时需要同时考虑到这两种形式。尽管具有最小( 1 ，k 1 ) 权 重的多项式是应用定理1 获得的，但是不能将这 1 个点使用简单的插值方式去获 得一样的插值多项式，而需要插值成独立互异的多项式。因此，需要将多项式集 进行扩展。最后的插值结果应获得一个多项式集，其中每一个多项式独立的对应y 中的一个测试矢量。 在开始对非普通元集合进行插值时，需要将算法2 获得的多项式g o 乒) 和g l ( x , z ) 去初始化算法3 的多项式对集合g o 。先做如下定义： w j 。= ( g ( z ，z ) ，岛( 工，z ) ) ( 2 4 6 ) w o ( o ) 为多项式对，并对g o 做出新的定义： g 。一) - w ) ( 2 4 7 ) 在插值的实施过程中虽然无需考虑插值的先后顺序，但是在这里假定按照候选位 置的划分顺序i l , 2 ，“进行插值。根据这一假定，在完成，步插值后将获得具有如 下形式的多项式对集合： 重庆邮电大学硕士论文第二章低复杂度c h a s e 型软判决译码算法的均堕堡! 里 g ，= w u ，w u ，一u ( 2 4 8 ) 其中，多项式对w f “) 由下式给出： w ：“= ( g 。( x ，z ) ，g 。( x ，z ” ( 2 4 9 ) 将第f 个长为z 的二元比特序列记为( b u 2 ， j ) 。因此，对于任意的j e 1 ，2 ，f ) ， 戬，o ( d 0 乒) 与，1 ( d ( x 力的根可以由以下两式给出： 吕。7 ( q ，彬+ 只胁) = ，“( q ，彬+ 以珊) = 0 若b 扩旬 ( 2 5 0 ) 吕，o d ( q ，彤+ 咒2 肿) = g ，。7 ( q 。，彬+ z 2 胁) = o 若b , j - - - 1 ( 2 5 1 ) 由于所有的二元多项式均是从w o ( o ) 开始构建，因此w b 。下式成立： 岛u ( 哆，+ 乃硒- - - g t j u ) ( ，+ y j 曲) = 0 ( 2 5 2 ) 从上文叙述可知，对于多项式对集合q 将含有2 t 1 个多项式对。其中，每一个多项 式对均是由y7 中的单一测试向量构造而成。构造g n 的过程可以由图2 2 所示的二 又树流程图形象表征。 算法2 集合b c 所对应候选位置的插值算法 具体算法流程 第一步，输入：( 磁拂皿，忱) ，v i b 。； 第二步，初始化多项式集合：g = 1 # ) ； 第三步，循环插值： f o r i e b c 多项式计算： ( q ，只) ：( ，( y i h d + 奶) v ( q ) ) 踟( ，只) 铷( 口；，只) 多项式选择： 如z ) = a r gm i n 酚力e g d e & l ，1 ) 悖0 声) ) ，g ( 0 q , y i ) 为) g 乒) = g 似力) 多项式更新： g o 乒) 2g 力+ ( 甙，只) 以q ，只) ) 俐 似歹黔0 【i ) = ，辑力 g = g o 力，g l 力) = g 力以力) ) e n d f o r 第四步，输出：g o = g o g 力，g l 歹) 重庆邮电大学硕士论文 第二章低复杂度c h a s e 型软判决译码算法的构造原理 心 j 之 w 0 ( 1 ) 乡 w o ( 2 ) w l ( 2 ) w o ( 1 1 。1 ) w l ( n 。1 ) j 杰 乡 w l ( 1 ) w o ( r i ) w l ( r 1 ) w 2 ( t 1 ) w 3 ( n ) 图2 2 二叉树插值 w 2 口一l l 玎一1 矽弋 w 2 口一2 玎w 2 口一l 蹿 在流程图中，对候选位置i t 的插值将由第厶1 层到，层的运算过程代替。比如： 在获取由第z 层结点g t = w 护，w i ( 0 ，w 2 f - 1 ) 所确定的多项式对时，需要将树枝 上所标示的数据点插入第厶1 层的结点g 厶l = w o ( 1 - ，w l ( 1 - ，w 2 1 1 t - 1 ) 所确定的多 项式中。显然，构造w 2 m ( 2 ) 和w 2 时1 是分别将候选位置对应的插值项： ( q 彬。+ 肋) ( 2 5 3 ) ( q + + 2 肋) ( 2 5 4 ) 插入多项式对w m ( 厶1 所获得的，即应用算法2 分别将各数据点插入到w m ( 厶1 所确定 的多项式中。二叉树插值过程所需要的计算复杂度取决于多项式运算及多项式更 新步骤，并且它的复杂度是对单一数据点进行插值的复杂度的两倍。然而，由于 在这些数据点中变量x 的取值均相同，因此可以通过将这些数据点联合起来进行 插值，以达到降低计算复杂度的目的。 由推论2 可知，以z 为变量的插值多项式度数不会超过l 。因此，可以将多项 式对w p l ) = ( 鼠o ( f - 1 ( x 力，g i , 1 ( 1 - i 0 ，z ) ) 表示成如下形式： g ，o “( 工，z ) = g o 。( z ) + z g o 1 ( x ) ( 2 5 5 ) g 1 - 1 ) ( x ，z ) = g 。( z ) + z g 。( x ) ( 2 5 6 ) 从算法2 可知，需要先计算各多项式在这些数据点的取值。因此，首先计算下列 1 9 矿警i 重庆邮电大学硕士论文 第二章低复杂度c h a s e 型软判决译码算法的构造原理 系数： c = 岛。( 。) ，c 1 = g o 。( 。) c l ，o = g 。( 。) ，c 1 1 = g l l ( 。) 接着计算出多项式取值： & 。卜1 ( ，。+ 肋) = c o + ( + 欺。“。) c o 1 乩g ( t - t ) ( + i ，十髓) - - c 1 o + ( + ) c 1 1 g ( i - 1 ) ( ，+ 。z r m ) _ c + ( + 2 ) 。c t l g ( t - t ) ( 。，。+ 2 舫) = c 。+ ( 。+ 2 ) 。c 1 1 ( 2 5 7 ) ( 2 5 8 ) ( 2 ( 2 ( 2 ( 2 5 9 ) 6 0 ) 6 1 ) 6 2 ) 对于单一的数据点，以上述方式对多项式进行计算时将只需要两次额外的乘法运 算。多项式更新步骤的运算复杂度也可以得到相应降低。为了证明这一设想，且 不失一般性，假定 d e g ( 1 - 1 ) ( 卜1 ( x ，z ) ) d e g ( 1 - 1 ) g r ( 1 - 1 ) ( 工，z ) ) ( 2 6 3 ) 接下来分别考虑三种不同的情况： 第一种情况，若插值项( 2 5 3 ) 和( 2 5 4 ) 均非多项式g g m ( 1 - 1 ) ( x ，z ) 的根。由算法2 的 运算规则可知，多项式选择时将使得： z ( 工，z ) = z 肋( x ，z ) = g 加u - 1 ( x ，z ) ( 2 6 4 ) 其中，厶( x ，z ) 和z 肋( 工，z ) 是分别由插值项( 2 5 3 ) 和( 2 5 4 ) 进行更新后得到的更新多 项式f ( x ，z ) 。由于多项式f ( x ，z ) 的更新只依赖于插值项中变量工对应的值，如： f ( x ，z ) = ( 工+ 口：i + 1 ) 厂( x ，z ) ( 2 6 5 ) 只需要进行一次更新运算，同时计算多项式g ( x ，z ) = g f ( x ，z ) ) 。 第二种情况，若其中有一个插值项是多项式& 。1 ( 工，z ) 的根。同样，为不失一 般性，假定： & 。u 1 ( + l ，+ ) = 0 ( 2 6 6 ) 因此，做如下选择： 厶( x ，z ) = g g f 1 ( i - i ) ( x ，z ) ( 2 6 7 ) z 肋( x ，z ) = g g ( 1 - 1 ) ( 石，z ) ( 2 6 8 ) 在这里，对f ( x ，z ) 的不同选择迫使这些多项式都需要进行更新。而对于多项式 g 肋( x ，z ) 则没有这个要求，因为： g n o ( x ，z ) = g 肋( x ，z ) + ( g 肋( + l ，+ + 。肿) 厶( 。，。+ ，胁) ) 。厶( x ，z ) ( 2 6 9 ) 其中，g 肋( + l + + 。胁) 。 因此，如前面所提到的只需要考虑四种情况中的三种。最后，考虑这两个数据点 均是多项式& 。( t - 1 ) ( x ，z ) 的根的情况。则必有： _ 肋( x ，z ) = 正肋( 工，z ) = g g “( 1 - 1 ) ( x ，z ) ( 2 7 0 ) 在这里，f ( x ，z ) 对每个数据点均等价，因此只需要做一次更新运算，即： 肋( x ，z ) = 正肋( x ，z ) = ( x + 。) f ( x ，z ) ( 2 7 1 ) 重庆邮电大学硕士论文第二章低复杂度c h a s e 型软判决译码算法的构造原理 当这两个数据点也是多项式g 肋( x ，z ) = g 肋( x ，z ) 的根时，无需考虑对它们的更新运 算。 从上述分析中可以知道，从w m ( ，- 1 构造w 2 m ( f 1 和w 2 m + l ( 厶1 的运算复杂度与对 单一数据点的插值复杂度相比，只有少许增加。对集合b u 所对应候选位置的插值 算法如算法3 所示。 算法3 集合b 。所对应候选位置的插值算法 具体算法流程 第一步，输入：( 吩抛h d ，h d ，鼽) ，v i e i , g c ； 第二步，初始化多项式对集合：g o = w o ( o = g 。； 第三步，计算：v j e 1 ，2 ，t 1 ) ，计算、= v ( 呸) 第四步，循环插值： f o ri e i 计算： ( y i ；，y i ；2 肿) = ( 瓯；+ 彬i ) v i ；，( y i i 2 1 d + 彬) v i ；) f o rm = 0 ，1 ，2 j - l _ 1 g7 = w ，1 ) 多项式计算：g o ( a i ，只肋) ，g l ( c t i ，只肋) g o ( a ；，只2 肋) ，g l ( a , ，只2 肋) 多项式选择： d ( x 力= a r gm i n 毋力g d e g o ，1 ) ( g 乒) ) ，g ( 0 4 ，只肋) 为) ) 五h d 力= a r gm i n 舭) e g d e g o ，1 ) ( g 力) ，g ( ，只2 肋) 为) ) g h d ( x , z ) = g 。 矗d 乒) ) 9 2 h d ( x , z ) = g 五h d o 力 多项式更新：g h d ( x , z ) = g h d 0 声) + ( g h d ( 0 i ，m 皿) f h d ( 0 q ，咒肋) ) 靠d 0 力 9 2 h d ( x z ) = h d o 声) + ( 9 2 h d ( o , i ，只2 肋) a h d ( o 【i ，只2 肋) ) 正h d o 力 f h d ( x 芦) = ”o 【i ) 俺d o 乒) a h d ( x 声) = ( 什嘶) 正h d 0 力 w 2 = ( g h d ( x , z v m do 力) w 2 m + l = ( 9 2 h d ( x z ) a h d 力) ) e n d f o r ) e n df o r 第五步，输出：g n 2 w o 仰，w 何，w 一，仰) 2 1 重庆邮电大学硕士论文第二章低复杂度c h a s e 型软判决译码算法的构造原理 2 。4 因式分解算法 利用2 2 3 中算法3 构造出多项式对集合q ，该集合中共包含2 q 个多项式对 w 椭，w 阳，一佃) ( 2 7 2 ) 其中，w ，是由测试向量y i 中莨所对应的候选位置进行插值获得的。从2 2 节中 推论2 可知，要求每一个测试向量所对应的插值多项式均具有最小( 1 ，1 ) 一权重。因 此，定义如下多项式集合： q = q o ( 工，z ) ，q l ( x ，z ) ，q 一。( z ，z ) ( 2 7 3 ) 其中 q ( x ，z ) = a r g m i n d e g ( 1 - 1 ) ( 6 ( 工，z ) ) 吼。o ( z ) + z 吼j ( z ) 且b ( x ，z ) w ，们 ( 2 7 4 ) 接下来，构建由所有候选位置插值完成的且满足2 2 节中定理1 要求的多项式， 即具有最小( 1 ，k 1 ) 权重的多项式。代换回2 2 2 节中的变量z ，可以获得如下多项 式集： q = q 0 ，z ) ，q 阮z ) ，锡一。o ，z ) ) ( 2 7 5 ) 其中 q f ( x ，z ) = q i o ( x ) v ( x ) + z q i 1 ( 工) ( 2 7 6 ) 应用推论1 ，可以直接从q ( 工，z ) 中得出以z 为变量的多项式。显然，候选信息多项 式亦包含在以z 为变量的多项式中。因此，按照上述方法可以得到一个具有才个 候选信息多项式的集合： m = m o ( z ) ，碗( x ) ，r h e , 一，( x ) ) ( 2 7 7 ) 然后从其中选出一个候选信息多项式作为译码信息输出。为了使得译码失败的概 率最小，可以选择满足： 豌o ) = a r g1 1 1 a 拳p ( 聊( z ) i ，)( 2 7 8 ) 的信息多项式而( x ) 。但需要注意的是，假若按照此方法来恢复信息多项式，不仅 运算复杂度高，对于高码率的r s 码尤为突出。而且所恢复出来的信息多项式是经 过了坐标变换后对应的多项式，要从该信息多项式恢复至原始的信息多项式将非 常困难。可以利用b m a 算法或类似钱搜索的方法对因式分解后的多项式进行运算 以捕获错误多项式，恢复出原始信息，如图2 3 和图2 4 所示。 文献【1 4 给出了一种恢复原始信息多项式的方法，但是该方法需要采取因式分 解算法，因此复杂度偏高。在第三章中，给出了混合多项式选择与因式分解的算 法。同时，结合这一算法给出了一种全新的译码结构，实现了原始信息的有效恢 复。 重庆邮电大学硕士论文第二章低复杂度c h a s e 型软判决译码算法的构造原理 一倍道榆 ! 一啸6 骨r - ”_ 一一 雄道检 图2 3 采用b m a 算法的l c c 算法流程 2 5 本章小结 图2 4 采用钱搜索及g m d 算法的l c c 算法流程 本章从编码方式、信道模型到实现译码的整个算法流程进行了详细的阐述。 尤其对译码部分的候选位置划分、测试向量集构造及其修改和插值算法等方面进 行了细化的剖析。分析了以变量替换为基础实现减小运算复杂度的坐标转换方法， 并以逐点插值算法为起点逐步引入简化插值方法，并对其中必要的定理和推论进 行了证明。 2 3 重庆邮电大学硕士论文 第三章基于m s f 的低复杂度c h a s e 型软判决算法 第三章基于m s f 的低复杂度c h a s e 型软判决算法 在第二章中详细的阐述了r s 码编码、a w g n 信道模型、测试向量集构造、候 选位置划分及多项式插值算法、因式分解的整个流程。坐标变换及重编码方法的 使用，能够极大的降低多项式插值及因式分解过程的运算复杂度，但是会带来信 息还原时的困惑。如若直接使用文献 1 4 】给出的方法，得到的将是经过变换后的信 息多项式，需要使用傅氏反变换进行转换。当码长较长时，解决傅氏反变换问题 将异常困难。本章在算法3 所示的简化插值基础上，提出混合多项式选择与因式 分解的方法并结合该方法得出新的译码结构。该译码结构能直接恢复原始信息多 项式，并在平衡运算复杂度的同时获得一定的性能增益。 3 1混合多项式选择与因式分解 本节给出混合多项式选择与因式分解方案及其必要分析，具体算法流程如算 法4 所示，下面展开对该算法的理论分析。 回顾第二章内容，我们讨论了在插值运算前利用坐标转换提取公共插值因式 的方法。这一方法带来的好处是使得每个插值二元多项式q ( x ，z ) 中以z 为变量的 多项式的度不大于1 ，所以该多项式的求解无需使用根搜索算法1 3 3 】。混合多项式选 择与因式分解方案选择的候选信息多项式z o ) 应具备下面这个性质，即z ( z ) 经估 值映射后得到的码矢量与硬判决码矢量弘的汉明距离应不大于( n k + 1 ) n 。因此，由 前文推论1 知z z ( x ) 能够整除q ( x ，z ) 。根据代数基本定理有： q ( 工，z ( x ) ) = 0 ( 3 1 ) 将( 3 。1 ) 等量代换( 2 7 5 ) 式后，有： 吼o ( x ) v ( x ) + q t 。l ( 石) z ( 工) = 0 ( 3 2 ) 求解方程( 3 2 ) 可得： z ( x ) ：型娑掣 ( 3 3 ) 吼1 i x ) 尽管z ( x ) 表示成商的形式，但一定是满足d e g ( x ) ) k - 1 的有效信息多项式。因 此，必定满足d e g ( ( x ) ) d e g ( q f l ( x ) ) ，下面对该不等式进行证明。 证明： 由( 3 3 ) 式可知 2 4 重庆邮电大学硕士论文 第三章基于m s f 的低复杂度c h a s e 型软判决算法 又因 d e g ( f ( x ) ) = d e g ( q ，。( 工) ，( x ) 】吼，l ( x ) ) d e g ( f ( x ) ) = d e g ( q ，o ( 工) ) + d e g ( ，( z ) ) 一d e g ( q f 。l ( 工) ) a e g ( v ( x ) ) = d e g ( 兀( x + 磁) ) = 后 其中i er ，将该等式与式( 3 5 ) 联合，有： d e g ( f ( x ) ) = d e g ( q f 。o ( x ) ) 一d e g ( q t 1 ( 工) ) + 尼七一1 ( 3 4 ) ( 3 5 ) ( 3 6 ) ( 3 7 ) 即： d e g ( q f o ( x ) ) d e g ( q f 。l ( x ) ) 一l ( 3 8 ) 所以有： d e g ( q i , o ( 工) ) d e g ( q f 1 ( x ) ) ( 3 9 ) 证毕。 1 主t ( 3 3 ) 知，吼。( z ) v ( 工) 应能够被g f 。( 工) 整除，将该结论记为。换句话说，吼，。( x ) 包含的不可约因式必定也是吼o ( 工) v ( x ) 的因式。由2 2 节中的式( 2 3 7 ) 知，v ( x ) 一 定不包含度大于1 的不可约因式。因此，吼。( 工) 所包含度大于1 的不可约因式也均 是吼。( 功的因式。所以在此不妨假定吼，。( 工) 所含不可约因式的度均为1 。由此，可 以将g f ，( x ) 表示成如下形式： 铂( 工) = 五兀( x 十) 兀( x + ，) ( 3 1 0 ) 胆y e 岛 其中名为g f ( 2 ”) 中的符号常量，4 为吼。( x ) 与v ( x ) 的公共根集合，尽为吼，( 工) 与 研。( 功的公共根集合。由于插值前进行了重编码转换，所以r 所对应候选位置的符 号均为o 。若i4 o ，则说明v ( x ) 中不存在被吼。，( x ) 消去的因式。换句话说，就 是尺所对应候选位置的硬判决没有发生错误；若1 4i 囝，对于任意4 中的元素吒 将消去对应于v ( 工) 中的因式 + 吼) ，这意味着有硬判决错误发生在位置点，将 该结论记为。