（应用数学专业论文）chase型译码算法的相关研究.pdf

中文摘要 2 一 在编码理论研究和实际的应用中 二元线性分组码译码是十分重要的 目前 许多迭代 软判决译码算法已经得到充分研究 其中大部分算法本质上都是在一系列由一个简单的内部 译码器 如代数译码器 迭代生成的候选码字中找出最好 或具有最大似然性 的码字作为 输出 一般而言 运用迭代软判决译码算法 内部的译码器可能在一些迭代中不能生成新的候 选码字 因此 这些迭代的执行会延长译码时延 从而 我们希望在不降低算法的错误性能 情况下尽可能多地减少迭代步骤 降低译码复杂度 通常 在每次迭代的最后 一些适当设 计的试验条件被用来控制迭代进程 除外条件和提前终止条件是这种试验条件中的两类 且 已经得到广泛运用 若除外条件满足 则在算法预先安排的一些迭代步骤中 内部译码器将 不能生成任何比此前得到的最好的候选码字还好的候选码字 因此可以跳过这些迭代步骤 提前终止条件可以被看作除外条件的最强形式 若除外条件满足 则剩下的迭代步骤不能改 进错误性能 从而可以终止迭代进程 本毕业论文讨论了一类迭代软判决译码算法 c h a s e 型译码算法 它的候选码字都是 利用限界距离译码围绕一些搜索中心而产生的 而这些搜索中心则是将硬判决向量添加到根 据接收向量的可靠性度量而确定的一些错误图样而得到的码字 原始的c h a s e 算法有三种不 同方案 分别称为c h a s e 算法l c h a s e 算法2 和c h a s e 算法3 近些年来 这些算法都得到 了改进和运用 其中c h a s c 算法2 在实际中用得较广泛 在论文第三部分针对一类c h a s e 型 译码算法进行了一些分析 并且设计了一些有效的试验条件 如最优条件和除外条件 还就 怎样在实际中运用这些条件给出了一些建议 关键词g m d 算法 m l d 算法 b d 译码 二元线性分组码 c h a s e 算法 c h a s e 型译 码算法 错误图样 试验条件 a b s t r a c t 3 一 t h ed e c o d i n go f b i n a r yb l o c kc o d e si sav e r yi m p o r t a n tp r o b l e mb o t hi nc o d i n g t h e o r ya n dp r a c t i c a la p p l i c a t i o n s of a r m a n yi t e r a t i v e s o f i d e c i s i o n d e c o d i n g a l g o r i t h m sh a v e b e e ns u f f i c i e n t l yd e v e l o p e d m o s to ft h e s ea l g o r i t h m sa r ed e v i s e dt o f i n dt h eb e s t o rt h em o s tl i k e l y c o d e w o r di nas e r i e so fc a n d i d a t e sw h i c ha r eu s u a l l y g e n e r a t e dw i t hs i m p l ei n t e r n a ld e c o d e r s s u c ha sa na l g e b r a i cd e c o d e r a st h eo u t p u t i ng e n e r a l f o ra l li t e r a t i v es o f t d e c i s i o nd e c o d i n ga l g o r i t h m t h ei n t e r n a ld e c o d e r m a y f a i l e dt og e n e r a t en e wc o d e w o r dc a n d i d a t e sa ts o m ei t e r a t i v es t e p s h e n c e t h e e x e c u t i o no ft h e s ei t e r a t i v es t e p sm a yp r o l o n gt h ed e c o d i n gd e l a y t h e r e f o r e i ti s d e s i r e dt or e d u c et h ei t e r a t i v es t e p sa sm a n ya sp o s s i b l ea n dt h ed e c o d i n gc o m p l e x i t y w i t h o u td e g r a d i n gt h ee r r o rp e r f o r m a n c eo ft h ea l g o r i t h m u s u a l l y a tt h ee n do fe a c h i t e r a t i v es t e p s o m em o r e s u i t a b l yd e v i s e dc o n d i t i o n sa r et e s t e dt oc o n t r o lt h ei t e r a t i v e p r o c e s s r u l i n g o u tc o n d i t i o n sa n de a r l yt e r m i n a t i o nc o n d i t i o n sa r et w oc l a s s e so f s u c hk i n do ft e s t i n gc o n d i t i o n sw h i c hh a v eb e e nu s e dw i d e l y i fa r u l i n g o u tc o n d i t i o n i ss a t i s f i e d t h e n i naf e ws u c c e s s i v ei t e r a t i v es t e p sw h i c ha r ep r e a r r a n g e db yt h e a l g o r i t h m t h ei n t e r n a ld e c o d e rc a nn o tg e n e r a t ea n yc o d e w o r dc a n d i d a t ew h i c hm a y b eb e t t e rt h a nt h eb e s tc o d e w o r dc a n d i d a t eo b t a i n e ds of a r a n dt h u st h e s es u c c e s s i v e i t e r a t i v es t e p sc a nb es k i p p e d a ne a r l yt e r m i n a t i o nc o n d i t i o nc a nb ev i e w e da st h e s t r o n g e s tv e r s i o no far u l i n g o u tc o n d i t i o n i far u l i n g o u tc o n d i t i o ni ss a t i s f i e d t h e n t h e r ei sn oi m p r o v e m e n to ne r r o rp e r f o r m a n c eb yt h ef o l l o w i n gi t e r a t i v es t e p s a n d t h u st h ei t e r a t i v ep r o c e s si st e r m i n a t e d t h i st h e s i sd i s c u s so n eo ft h ei t e r a t i v es o f t d e c i s i o nd e c o d i n ga l g o r i t h m s c h a s e t y p ed e c o d i n ga l g o r i t h mw h o s ec o d e w o r dc a n d i d a t e sg e n e r a t eb yb o u n d e d d i s t a n c e b d d e c o d i n ga r o u n dt h ew o r d s c a l l e ds e a r c hc e n t e r s w h i c ha r eo b t a i n e d b ya d d i n gh a r d d e c i s i o ns e q u e n c e st og i v e ne r r o rp a t t e m sw h i c ha r eb a s e do nt h e r e l i a b i l i t y o f r e c e i v e ds e q u e n c e s t h e o r i g i n a lc h a s ed e c o d i n ga l g o r i t h m sa r e c h a s e 一1 c h a s e 一2a n dc h a s e 一3 i nr e c e n ty e a r s t h e s ea l g o r i t h m sh a v eb e e ni m p r o v e d a n da p p l i e d a n dc h a s e 一2i sa p p l i e dm o r ew i d e l yt h et h i r dc h a p t e ro ft h i st h e s i s a n a l y z eac l a s so fc h a s e t y p ed e c o d i n ga l g o r i t h m a n dd e v i s es o m ee f f e c t i v et e s t i n g c o n d i t i o n sf o ri ts u c ha so p t i m a l i t yc o n d i t i o n sa n dr u l i n g o u tc o n d i t i o n s a n da l s o g i v es o m es u g g e s t i o n sa b o u th o w t ou s et h e s ec o n d i t i o n s 4 一 k e yw o r d sg e n e r a l i z e d m i n i m u m d i s t a n c e g m d d e c o d i n ga l g o r i t h m m a x i m u m l i k e l i h o o dd e c o d i n g m l d a l g o r i t h m b o u n d e dd i s t a n c e b d d e c o d i n g a l g o r i t h m b i n a r yl i n e a rb l o c kc o d e c h a s ed e c o d i n ga l g o r i t h m c h a s e t y p ea l g o r i t h m e r r o rp e r f o r m a n c e t e s t i n gc o n d i t i o n 扬州大学硕十学位论文 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 本人声明 所呈交的学位论文是在导师指导下独立进行研究工作所取得的研究成 果 除文中已经标明引用的内容外 本论文不包含其他个人或集体已经发表的研究成 果 对本文的研究做出贡献的个人和集体 均已在文中以明确方式标明 本声明的法律 结果由本人承担 学位论文作者签名 互晖未 签字日期 一口衫年多月 口日 学位论文版权使用授权书 本人完全了解学校有关保留 使用学位论文的规定 即 学校有权保留并向国家有 二关部门或机构送交学位论文的复印件和电子文档 允许论文被查阅和借阅 本人授权扬 州大学可以将学位论文的全部或部分内容编入有关数据库进行检索 可以采用影印 缩 印或扫描等复制手段保存 汇编学位论文 同时授权中国科学技术信息研究所将本学位 论文收录到 中国学位论文全文数据库 并通过网络向社会公众提供信息服务 z 学位论文作者签名 工咩充导师签名 誓刁芝 签字日期 夕哆年 月 p 日签字日期 厉乃年6 月1 0 日 l 千晖东c h a s e 型译码算法的相关研究 1 引言 1 1 数字通信系统模型 数字通信系统是以数字信号的形式来传递信息的一种通信系统 它所包括的范围很 广 从现在的市话通信系统 数字蜂窝系统 计算机通信系统到雷达系统 计算机运算和 存储系统等都是数字通信系统 所有数字通信系统都可归结为如图卜l 所示的模型 图卜1 数字通信系统模型 图1 1 中 信源编码器把信源发出的消息如语言 图像 文字等转换成为二进制 也可以转换成为多进制 形式的信息序列 并且为了使传输有效 还去掉一些与传输信 息无关的冗余 有时为了保密 信源编码器后还可以加上加密器 为了抗击传输过程中的 各种干扰 往往要人为地加上一些冗余 使系统具有自动检错或纠错能力 这种功能由图 中的信道编码器即纠错编码器完成 调制器的功能是把纠错编码器送出的信息序列通过调 制器变换成适合于信道传输的信号 数字信号在信道传输过程中 总会遇到各种干扰而使 信号失真 这种失真信号传输到接收端的解调器进行解调 变成二进制 或多进制 信息 序列 由于信道干扰的影响 该信息序列中可能已有错误 经过信道译码器即纠错码译码 器 对其中的错误进行纠正 再通过信源译码器 及解密器 恢复成原来的消息送给用 户 从上可知 信道编码是用来控制有扰信道对信息序列所产生的差错的 故也称为差错 控制编码 通常俗称纠错码 其实纠错码不光用来纠错 也用来检错 差错控制编码技术 是为提高数字通信系统的可靠性而建立的一门信息处理技术 随着信息时代到来 它现已 成为一门标准技术而广泛采用 由于我们所关心的只是图卜1 中的信道编 译码器两个方框 为了研究方便 将上 述模型再进一步简化成图卜2 所示的模型 5 一 扬州大学硕 学位论文 图卜2 数字通信系统简化模型 1 2 通信信道 在图卜2 数字通信系统简化模型中 信源是指原来的信源和信源编码器 其输出是二 进制 或多进制 信息序列 信道是包括调制器 解调器 传输设备和实际信道 或称传 输媒质 在内的编码信道 也称广义信道 其输入一般是二进制 或多进制 数字序 列 而其输出可以是二进制 或多进制 的数字序列 也可以是未量化的实数序列 而图 中的信宿可以是人或计算机 1 离散无记忆信道 首先讨论编码信道是离散信道的情况 离散信道是输入和输出序列取值都是离散值的 信道 离散信道可分为无记忆信道和有记忆信道 无记忆信道又称为随机信道 它产生随 机错误 这种错误的特点是各码元是否出错是相互独立的 即每一个差错的出现与其前后 是否有错无关 卫星信道和深空信道可近似看成是随机信道 而有记忆信道又称突发信 道 它产生突发错误 这种错误往往不是单个地而是成群成串地出现的 也就是一个错误 的出现 往往引起其前后码元的错误 表现为错误之间相关性 如高频 散射 有线等信 道就可看做有记忆信道 但是由于实际信道干扰的复杂性 错误往往不是一种 而是两种 并存 随机错误和突发错误并存的信道叫组合信道或复合信道 下面考虑离散信道的数学模型 它可用信道的输入输出统计关系定义 即用联合条件 概率p 1 i c 来描述 这里 u p 屹一 表示信道输出序列 h q 而 c c o c 巳一 表示信道输入序列 q f 通常信道输入符号集f o l 而信道输 出符号集q 要依据译码方式而确定 如果信道是无记忆的 则 h l p y l c 兀p ic j 1 1 i 0 我们最常研究的就是离散无记忆信道 简记为d m c d i s c r e t em e r n o r y l e s sc h a n n e l 既然 信道是无记忆的 则在任何时刻信道输出只与此时的信道输入有关 而与以前的输入无 关 对于d m c 如果对于任意f 和歹 以及任意a f 和b q 均有 6 一 于晖东c h a s e 型译码算法的相关研究 尸 h 6 i q 口 尸 b 巳 口 1 2 则称此信道是平稳的 一般情况下若无特殊声明 所讨论的d m c 都是平稳的 这样在离 散无记忆条件下 我们只需研究单个符号的传输 即d m c 数学模型可用下面一组称为转 移概率的条件概率来定义 p b t 臼 l b q a e f 1 3 设f 口l 哆 a s 和q 6 l 6 2 阮 记弓 p 屯k 则该信道数学模型也可用矩阵 弓 来描述 它称为该信道的转移概率矩阵 2 二进制对称信道 在二进制硬判决情况下 即f q o 1 时 则信道转移概率矩阵为 尸p ll i o 窨尸e llill c 一4 i j 如果e 0 1 0 e 0 1 1 p 则称这种信道为二进制对称信道 简写为b s c b i n a r y s y m m e t r i cc h a n n e l 3 二进制删除信道 在二进制删除判决情况下 即f o 1 和9 0 x 1 时 如果还有 p 0 1 0 p 0 1 0 p 且尸 z l o 尸 工1 1 g 成立 则称这种信道为二进制删除信道 简写为 b e c b i n a r ye r a s u r ec h a n n e l 在有删除处理情况下 信道的转移概率p 一般很小 可以 忽略 此时称为二进制纯删除信道 以后所说的b e c 都是指这种信道 应当指出 当码 元作删除处理时 它在序列中的位置是已知的 仅不知其值是0 还是1 故对这种b e c 信道的纠错要比b s c 信道容易 4 离散输入 连续输出信道 假定信道是无记忆的 且输入符号集仍然是一个有限 离散的集合 f q a 2 q 而信道 检测器 输出是未量化信息 这时译码器输入可以是任意实 数 即o 棚 悯 定义 t 一 口 大土i j 为时间离散的连续记忆信道 它的特性由 离散输入彳 连续输出b 以及一组条件概率密度函数 尸 b 6 i 彳 口 l f 1 2 来决 7 一 扬州大学硕十学位论文 8 一 这类信道中最重要的一种是加性高斯自噪声a w g n a d d i t i v ew h i t eg a u s s i a nn o i s e 信 道 对它而言 信道输出为 b a f l t g 卜5 式中甩g 是一个方差为n o 2 均值为0 的高斯随机变量 于是输入为q 输出为6 的条件 概率密度函数为 e b l 赤p 们m 1 6 在二进制软判决情况下 如果信道输出为输入与高斯白噪声相加 则称这种信道为 二进制输入加性高斯白噪声信道 为了便于在a w g n 信道上使用软判决 将信道输入发 送码的符号表示为 1 或 口 而不表示为对硬判决有利的0 和1 1 3 最大后验概率译码与最大似然译码 在有噪声信道中传送信息是会发生错误的 错误概率和信道统计特性 译码过程以 及译码规则有关 定义卜1设编码信道输入码字集为f 订 f 1 2 m 其输出的序列集为 v 1 2 n 可以取为无穷大 若对每一个输出序列y o 都有一个确定的函数 d 使v o 对应于唯一的一个输入码字c f 则称这样的函数为译码规则 记为 d v u c f f 1 2 m j l 2 n 卜7 显然 对于有m 个输入 n 个输出的信道而言 按上述定义得到的译码规则共有m 种 在确定译码规则d 之后 若编码信道输出v 则它一定可译为c 如果信道输入的 就是c 则意味着译码是正确的 反之 则意味着译码是错误的 于是此时 在译码器 收到v o 的情况下 正确译码的条件概率为 p d 0 u 抄 p v o 1 8 而错误译码条件概率为 p p p 1 一p d v o p 1 一p c 0 p 1 9 从统计角度讲 平均译码错误概率为 e p pv o 兰p p p 选择译码规则总的原则就是使忍达到最小i 1 欲使 最小v o 则使式 1 1 0 中和式的每一o 项 l 达o 到最小即可 由于尸 v 1 与译码规则无关 故要使 最小 必须使尸 d v 1 p 达到最 千晖尔c h a s e 刑译码算法的相关研究 大 于是引出最大后验概率m a p m a x i m u ma p o s t e r i o r i 译码方法 定义1 2 选择译码规则d v 1 c i 2 使之满足条件 9 一 尸 c 圳v o p c o p 矧 2 m i 1 1 则称之为最大后验概率译码 最大后验概率译码是一种最佳译码策略 因此采用最大后验概率译码性能将会达到 最优 但译码复杂度也会达到最高 3 采用著名的b c j r 算法就可实现最大后验概率译 码 4 人们在对t u r b o 码进行译码时 经常使用的译码方法之一就是b c i r 算法 但一般来说 后验概率是难以确定的 所以应用起来并不方便 为此需要引入其它 译码方法 由贝叶斯 b a y e s 公式可知 式 1 1 0 可写为 一p v 笃掣 m m 均 7 j 1 j 1 11 7 于是 有 p 0 7 j c p c 尸 v j l c 国 尸 c f 1 2 m i 1 3 当信道输入为等概率分布时 即 尸 c 川 尸 叫 则有 尸 v u p v o i i 2 m i 1 2 m 1 1 4 定义1 3 选择译码规则d v p c l 2 使之满足式 1 1 3 则称之为 最大似然译码m l d m a x i m u ml i k e l i h o o dd e c o d i n g 而p v 叫c j i 1 2 m 称为c 0 对y d 的似然函数 当信道输入为等概率分布时 就可用式 1 1 4 进行最大似然译码 而式 1 1 4 中条件 概率就是信道转移概率矩阵中的元素 通常用式 1 1 4 来进行译码 但当信道输入不是等 概率分布时 采用式 1 1 4 进行译码尽管方便 但并不是最佳译码 著名的v i t e r b i 译码算法就是一种最大似然译码算法 1 卷积码广泛地使用它来进行 译码 扬州大学硕十学何论文 2 迭代软判决译码的基本理论 2 1 软判决译码的基本概念 为了能有效地利用接收信号波形中的信息 使译码器能以更大的正确概率进行译 码 人们提出了软判决译码的思想 若译码器直接利用解调器输出的未量化的模拟电压或其变换进行译码 则称这种译 码方式为模拟译码 而若把解调器输出的抽样电压先进行o 2 m 1 1 电平量化 再送 给译码器进行译码 则称这种译码方式为 q 进制 数字译码 无论是模拟译码还是数 字译码 统称为软判决译码 通常我们只考虑离散无记忆 d m c 信道 一般若信道中的噪声仅为加性高斯白噪声 a w g n 则模拟译码对应的编码信道就为二进制输入加性高斯白噪声信道 简称 a w g n 信道 而数字译码对应的编码信道为二进制输入q 进制输出的离散无记忆信道 简称q 进制输出信道 这两种信道模型是软判决译码研究最常采用的信道模型 2 2 软判决译码的距离函数 h a m m i n g 距离为基于硬判决译码的编码系统性能分析提供了方便 下面将考虑适合 软判决译码的距离函数 1 欧几里德距离 设系统采用一个g f 2 上 2 七 线性分组码f 编码信道是均值为0 方差为 盯2 o 2 的a w g n 信道 令c c o q 巳一1 是f 的某一个码字 其中c i g f 2 码字 c 所对应的调制器 如b p s k 调制 输出序列则可表示为李 磊 磊 己一 其中 互 一1 p e 巨表示信号能量 令v v o h 9 o 屹一 表示信道传送一个码字后响应的 接收序列 这里v r r 为实数集合 定义2 1 码字c 和接收序列v 之间的欧几罩德距离 简称欧氏距离 定义为 月一l d e v c v 一瓦 2 2 1 面 同时定义d e o c i v 一瓦 2 为码元的欧式距离 下面的定理揭示了欧氏距离和最大似然译码之间的密切关系 定理2 1对于二进制输入加性高斯白噪声信道 如果信道输入码字为等概率分布 则其 最大似然译码可以等价于最小欧氏距离译码 证明在a w g n 信道下 对于一个发送码字c c c 川 和一个接收码组 y v v 川 其似然函数为 干晖东 c h a s e 型译码算法的相犬研究 删c 鲫c f 蘑等2 丽e d e v c n o 2 2 显然 d e o c 越大 似然函数p c 越小 因此求最大似然函数学西i c 的问题就转化为 求最小欧氏距离m i n d c 的问题 2 软判决距离 实际的通信系统往往都要把解调器输出的抽样电压先进行q 2 似 1 电平量化 再 送给译码器进行译码 虽然量化电平越多 译码性能越好 但一般用8 电平或1 6 电平量 化 译码性能就很好地接近量化时的性能 1 在a w g n 信道中 b p s k 相干解调系统的均匀8 电平量化情况分别描述的是相干匹 配滤波器输出的条件概率密度函数 酬 警 和 d v l l 等 式中 v 表示相干匹配滤波器输出的抽样电压值 e 为信号能量 n 2 是噪声方差 注 意 码元1 和0 分别对应电压值 百和一厄 经过8 电平量化而形成的编码信道是二进 制输入八进制输出的离散无记忆信道 这是一种对称信道 满足 p i o 尸 匆一j 一1 1 1 q 8 j o 1 7 2 3 其中 p u i c x c l 2 表示信道转移概率 它等于给定输入为c 时输出电压幅度v 落在电平 区间 的概率 例如 p 2 l o p 5 1 1 对于一般二进制输a q 进制输出的离散无记忆信道 其信道特性完全由信道转移概率 p u c 0 1 q 一1 c 0 1 所确定 在b s c 中 有h a m m i n g 距离和h a m m i n g 重量两个重 要概念 下面将在一般q 进制输出信道中推广这两个概念 在b s c 中 一个码元c 的h a m m i n g 重量为比 c 而在q 进制输出信道中 为了研 究方便 定义发送码元c 的软判决重量为 毗g 一l 2 4 在此基础上 定义发送码元c 与接收码元 之间的软判决距离为 d 0 c l j w s c t j 一 q l k i 2 5 这种定义基本上能反映出接收码元相对发送码元的似然函数值之比 1 定义2 2 令c g c c 州 表示一个码字 c g f 2 而 几 j 川 表示信道传送 一个码字后相应的输出序列 o 1 q 一1 则码字c 和输出序列 之间的软判决距离为 扬州大学硕七学何论文 d e o c d c 2 6 i o 显然 q 进制输出信道中的软判决距离是b s c 中的h a m m i n g 距离概念的自然推广 类似于定理2 1 有如下的定理 1 8 定理2 2对于二进制输入q 进制输出的离散无记忆信道 如果信道输入码字为等概率 分布 则其最大似然译码可以近似等价于最小软判决距离译码 显然 在a w g n 信道中 最小软判决距离译码性能不如最小欧氏距离译码性能 但 随着q 变大 最小软判决距离译码性能将趋近最小欧氏距离译码性能 在q 进制输出信道中 令c c o c c 川 表示发送码字 而j 伉 j i 一 表示相 应的接收码组 定义发送码字c 与接收码组歹的软错误图样为 p 0 o c 0 d d c l l d 一 c 一 2 7 软错误图样p 的软判决重量 简称软重量 定义为 w j g d c d c 2 8 面 下面的定理揭示了码的纠错能力与软判决距离之间的关系 定理2 3 对于一个g f 2 上k 后 线性分组码f 若最小距离为d 则最小软判决距离为 一1 p 该码可纠正软重量为t 0 z 垒 i 0 产1 2 当1 时 z 的可靠性可以用h 来检测 因为川与z 的对数似然率成比例 取甜 强 甜2 甜 v v 且 与 的关系如下 m 2 u 一1 k 3 1 i l 则对码字c q 乞 知 c 越大 m c 越大 c 被传输的可能性就越大 另定义 q u a i u i 刁 1 i n 哦 垒 1 2 口 三 垒 川 i e q u j f l j 3 1 3 2 和 3 4 m u 可表示为m z 和l u 的表达式 m u 2 u 一1 k 3 2 3 3 3 4 2 1 k 一 2 2 k i 1i 1 m z 2 l u 这里l u 1 称为关于硬判决序列z 的u 的相关偏差 对y 的任意子集r 定义 互 r 垒z l l i n rl u 且规定量 囝 垒 m l d 可以用相关偏差表述如下 译码器将接收到的序列 译成最优码字乞 c 且 满足 互 c 若z 是一个码字 因为对任意的甜 矿 o 三 z 所以z 是 最优码字 用i d a 表示c 上的软判决迭代译码算法 若二元硬判决序列z 在c 中 则z 被译码 字被输出 同时译码进程终止 否则 i d a 从第1 次迭代开始 在第 次迭代中 i d a 运 扬州大学硕士学位论文 行f 列两个子程序 g 和 t g 候选码字的生成 内部译码器在区域尺 上搜索 寻找满足 c 川 量 尺 n c 3 5 的最好码字c 这罩c 表示在第 次迭代中生成的候选码字 若尺 n c a 则在第j 次迭代 中没有候选码字生成 在这种情形下 c 没有定义 记作木 且规定三 宰 垒 定义 r p 歹 垒壹足 f 3 6 且规定 r m a u r i 3 7 当l c c 时 我们称候选码字c 好于候选码字c 在具体的候选码字集合中 若三 c 能够取到最小值 则称候选码字c 是最好的 记 是r p j o c 中的最好码字 满足 川 红rp j o c 3 8 且规定当r p 厂 c f d 时 t 终止条件的检测 若有新的候选码字生成 则终止条件 简写为c o n d r 将会被 检测 若满足c o n d r 则巳删 被输出且为被译码字 同时译码进程终止 若输出的是 则i d a 译码失败 若没有新的候选码字生成或不满足c o n d r 则i d a 进行第 j 1 次迭代 下面给出一些有用的记号 r e i l i j n 定义 l 歹 i i 1 歹 x u 甜 v v l v v n 及非空集 1 n 定义 如 甜 v 鱿f 一 i 3 9 对 之 1 之 定义 p l z f 垒 r 卅k 3 1 0 将九 1 u v 川 甜 y 巧川 分别简写为以 z v 九 甜 v b 为了方便 假设 的第1 2 n 位按照如下的可靠性顺序排序 川 g p l 时 x j 为x u o o 对u v 和正整数d 定义 q 秘 垒 v y 九 v 矗 3 1 2 o d 甜 垒 v y 九 叩 d 3 1 3 3 2 一般最优条件 若i d a 是m l d 算法 终止条件c o n d r 通常被选为最优条件 记作c o n d o p t 若在某 迭代中c o n d 印 满足 则最近得到的最好的候选码字就是最优码字 有效的c o n d 叫能快 速终止迭代进程 下面我们首先给出能运用于任意基于一系列生成的候选码字上的i d a 的一般c o n d 印 则 歹 的在r p 上的运用就显而易见了 我们称 u 为参考码字 且坼 v 1 f 办 称而 q i e 整数4 d 2 d h 为参考 距离 现在给出一个基于这些参考码字和参考距离的c o n d o 尹 记 噬 以 乡 iu 一 u i 产i h 一 2 盆d d 甜 j 下面给出如下引理 引理3 1 若u 一 一 的 满足 y y 幽 v 乃 l j j j 除外条件记作c o n d 胄d 将被试验 若c o n d 足d 满足 则在第 1 次 迭代和第歹 次迭代之间 内部译码器不可能生成任何比 吲 歹 还好的候选码字 从而可 以跳过这两次迭代 o o 除外条件也可以称为提前终止条件 记作c d 甩d 盯 以下的引理借助集合足p p 给出了一个c o n d 膏d 引理3 3 对j j 及u r p j c c 三 川 互f 彤 川r y u i 3 1 9 是一个 除外条件 式 3 1 9 将在c h a s e 型译码算法中会得到进一步研究 干晖东c h a s e 犁译码算法的相犬研究 4 一类c h a s e 型译码算法的试验条件 对于码字删 正整数气和f 满足o t o 卜 一 j 和1 娜 嘶定义一类 c h a s e 型译码算法 记作c h a s e 1 t o r 其候选码字是由限界距离为乇的内部译码器围绕 v e 产生的 这里e 称为试验错误图样 为其非零分量限制在前f 位的所有向量 c h a s e v l a o i 一o 2 l 氏 2 j 是最初的c h a s e 一2 译码算法 7 下面考虑为c h a s e v t f 提供一些有效的试验条件 为了简便 假设试验的错误图 样以二元序列的形式生成 用p 1 2 7 表示第 个试验的错误图样 则 p p 以 p o o 是矿 中 元序列 且满足 p a 2 h j 1 4 1 i l 在第j 次迭代中 其搜索区域为 r 材 y 九 州 川 4 2 这里v 墅 p 称为第j 次迭代的搜索中心 我们将运用 3 1 7 3 1 9 及下面的引理给出c h a s e v t o r 一些具体的试验条件 引理4 1 i 当i f i 时 有 r p 2 卜1 u v 如m 州 o 4 3 2 当2 卜1 歹 2 1 z f 时 有 r p 2 卜1 p ev a 局 f v 川 如 f o 4 4 3 当2 卜1 2 7 1 f 时 有 r j r e 2 卜1 n 尺 2 卜1 a 4 5 4 1c h a s e v t o f 的最优条件 当1 f 1 时 由 4 3 扬州人学硕十学位论文 y p 2 卜1 p y e l i 甜 届 小 川 d m t o 若u 是足p 2 h r c 的一个子集 则由 3 1 7 和 4 6 4 6 l c b e 2 h 量 ue 矿 t o l n y u 4 7 是ec h e s t 2 卜1 的一个c o n d 卵 现在 我们考虑给出 2 h 歹 2 1 f 的一些c o n d 印 因为 q 胪哗 2 n u b 纠r f 由 4 2 和 4 3 得 y p 似 v a 州 1 4 v o 1 v o t o 1 2 卜1 f 4 8 若 是r p j n c 的一个子集 则由 3 1 7 和 4 8 得 9 妇 互 材 v 甜 f 0 1 1 f o l 2 卜1 f n y 4 9 是 的一个c o n d 叫 若u 包含候选码字c f 2 卜1 f 则我们可以忽略 4 9 右边 d n f 对最终结果的影响 且由 4 3 4 4 和 4 5 得 y 胪v p 2 u 2 7 叫 矿 略 u v 气 1 u 于是得到 4 9 的另一种形式 u i 2 1 小y a 2 p v v f 川 叩 f o 上 c 6 删 r n j n 量 y v l ny 4 1 0 j m i i n 2 tm 沁矿 局 如 a v f 州 t o nv 4 1 1 千晖东c h a s e 犁译码算法的相关研究 注意到由 4 9 给出的c o n d 叩 或由 4 1 1 给出的c o n d 叫 只对 一2 或 2 一 是小整数时适用 否则 4 9 或 4 1 1 右边的计算复杂度会很大 若2 卜1 j 2 卜1 2 r 一 i 则 4 1 1 可以写成一种更方便计算的新形式 因为整 数f 满足2 卜1 2 r 1 t o 1 u 甜 矿 d m 一 材 v 1 u 如 甜 v f o u 川 爿 卜y p l j 甜 a v f 如川 州 岛 所以 x c r p n c 的任意子集 厂 l c b 翻 歹 1 1 1 i n 互 v 1 如 u v 岛 1 r 矿 量 y 如川一 v l 嘶 u 幽 v f r y 兰m 一i n h 量 矿 t 9 2p l v f l v r o r 矿 材 4 1 2 是 其中2 卜1 2 卜1 2 i 1 1 l 的一个c o n d 叩 当正整数2 卜1 2 阳 j 很小时 4 1 2 给出的c o n d 叫是适用的 特别地 若 j 2 卜1 2 r 则 4 1 2 给出了 2 卜1 2 卜1 如下的c o n d 叫 l c b 酬 2 h 2 卜1 1 1 1 i n q 扯y 如川 岛 l n 矿 甜 出 y 川一 州 l 砷 如 州 r r y 甜 显然 对任意的f 及b 厂 c 的子集u 三 川 缸 矿 u f ny 也是 的一个c o n d 印 禾1 3 4 1 4 扬州大学硕十学位论文 根据 4 1 4 我们可以进一步得到一些有用的c o n d 印 例如 若对某 7 1 7 有2 卜1 2 一 歹 t o 1 nv 材 出扰 y 只h 州 1 幽 v f d h f w f n y 甜 4 1 是 的一个c o n d 印 对任意的 2 卜1 2 7 及彤 n c 的子集u 三 巳鲥 川 4 y 2 h n 矿 甜 量 y m l n y z 4 1 6 也是 的一个c o n d o v t 4 2 c h a s e v t o f 的除外条件 对整数 乞和 o 2 f 有整数i 满足2 h 2 f 2 h 2 2 当且仅当 既 l 如 p f 不是 乞一f 1 全零序列且 巩扎 p f 晚扎 p 2 t i 1 巩扎 p 2 t 2 如 因此 由 4 4 和 4 5 有 巧 2 卜1 2 如 r p 2 卜1 2 矿肛d h l 1 f 2 叫 l 吼扎小 巩刖 v 2 t l 2 乞 d n 川 t o 若u r p 2 h 2 n c 的一个子集 则由 3 1 9 和 4 7 得 2 h 2 互 u ey 肛d h 小i f 2 1 4 一1 7 饩 小 p t 小 2 h 2 如 d n 川 叩 0 n 矿 4 1 8 千 晖东c h a s e 型译码算法的相关研究 是一个 2 卜1 2 2 卜1 2 如 除外条件 对 o 一1 歹 2 h 一1 2 h 可知整数埔旨足 2 7 f 4 1 9 若 是r p 洲2 n c 的一个子集 由 3 1 9 和 4 4 得 n 2 红 u e y p r u 肌 小 2 r 1 如地 o n v 4 2 0 是一个 2 r 歹 1 2 r 除外条件 若 7 o 则2 h 2 j g l 4 2 0 给出了一个 1 除外条件 互 扰 矿 p i 甜 a v 1 如川 甜 1 t o nv u 若 1 1 则 1 和 4 2 0 给t bt 一个 2 h 2 7 除外条件 因为 4 2 1 吲 2 h 互 ue 矿 嘶 功 如川 f ny 材 4 2 2 r p 2 7 p 2 1 芝 r p 2 p 2 h 芝 即 y u i 一 如川 训 f 0 若u 是足 2 h 厂 c 的一个子集 则由 3 1 9 得 t c b 蹦 2 啤量 矿 m 以川 弦 训 ny 4 2 3 扬州人学硕十学位论文 是第2 卜1 次迭代的一个c o n d 盯 显然 对i 和r p j c c 的子集u c 6 删 川 红 r p p f n y 4 2 4 也是一个 歹 歹7 除外条件 根据 4 2 4 还可以进行一些有用的c o n d r o 的深入研究 例如 对j 2 歹 1 2 其中0 l l 1 2 卜 一1 2 卜7 和r p j r c 的子集 u 上 耐 川 量 2 h 2 2 p 2 h 刺 r y 互 y 如小 v l 饩刖 掰 吼 v 1 2 r l 甜 1 岛 n 矿 4 2 5 是一个 2 卜1 2 除外条件 对 州2 1 2 其中o z l 1 2 m 一1 2 h 及r p j t n c 的子集u 三 耐 硝 4 巧 1 2 r 2 1 n 矿 群 e ue 矿 肌v 肌 小 1 2 1 甜 1 o n y 4 2 6 是一个 歹 歹 0 2 除外条件 对2 卜1 2 及灭p 歹 n c 的子集u k 州 红 b 2 2 h n y 砧 量 v m 蟊 n z 1 岛 n 矿 4 2 7 是一个 2 除外条件 4 3 试验条件的实际应用 在4 1 和4 2 中 给出了c h a s e v t o f 的一些试验条件 下面就怎样在实际中运用 这些条件给出了一些建议 1 在第2 卜1 次迭代中 试验 4 7 当2 h 2 时 一个c o n d 叫被试验当且仅当 最好候选码字被更新 即已删 c b 一1 c o n d 叫可行的顺序是 4 1 6 4 1 5 4 一 干晖东c h a s e 利译码算法的相关研究 1 2 4 1 1 4 9 2 因为 4 1 4 中集合u 可选为r i n c 的子集 所以在第 次迭代i j 评估的最强 的c o n d 卵 也是 歹 最优性的充分条件 且在其它c o n d 叫被试验前被试验 3 在第2 卜1 次迭代中 建议找一个尽可能大的整数厶 0 一1 使得 4 2 0 成 立 其中z 歹 2 卜 若这样的整数z 不到 则执行围绕1 i2 扣1 1 的限界距离为t 的 译码且设f l 0 随后建议找一个尽可能大的整数 2 l 1 使 4 1 8 成立 若这样 的整数 找不到 执行连续的迭代直到最好的候选码字被更新 否则 建议找一个尽可 能大的整数 o 使得 4 2 0 成立 其中 j 7 2 卜 1 2 如一 依次类推知直到最好 的候选码字被更新 其最优性也被试验了 若不满足最优条件 则试验 4 2 7 若 4 2 7 试验有误 建议寻找一个尽可能大的整数厶 使 4 2 5 成立或尽可能大的整数 使 4 2 6 成立 若这两个整数都找不到 则执行限界距离为t 的译码直到最好的候选码字被更 新 依此类推 4 因为在 4 2 4 中 集合u 可以是足 i n c 的子集 所以在第歹次迭代前所有被 赋值的 f j f 除外条件中的最大值也是 j 除外条件 且建议在其它 j j 除外条 件试验前试验 5 关于r p n c 的子集u 的选取 因为当l u i 增大时试验条件的计算复杂度也增 大 所以 通常被选为r j r c 的小子集 例如