（计算机软件与理论专业论文）群码的极小trellis及tailbiting+trellis.pdf

摘要 本文系统地论述了极小t r e l l i s 和t a i l b i t i n gt r e l l i s 理论，并将线性码的t r e l l i s 在有限域上的些性质推广到了有限交换群。 t r e l l i s 图是一种可以提高通信系统解码效率的重要工具，在信息论编码论和 密码学领域有重要作用。按照极大似然译码的原则，通过v i t e r b i 算法可以对t r e l l i s 进行高效的译码。因此，t r e l l i s 理论的中心问题就是如何构造最简单的t r e l l i s ，即 所谓极小t r e l l i s 。 线性码的极小常规t r e l l i s 图通过它的生成矩阵或较验矩阵已经得到很好的解 决，即线性码的极小常规t r e l l i s 一定可以通过极小跨度形式的一组基来生成，而 且这组基的跨度集合是唯一的。一些例证已经表明，t a i l b i t i n gt r e l l i s e s 的复杂度 比最好的常规t r e l l i s 要低，因而它可以更快地进行解码。一般的极小t a i l b i t i n g t r e l l i s e s 仍未解决，但线性t a i l 一b i t i n gt r e l l i s e s 有结论：任意线性码的线性t a i l - b i t i n g t r e l l i s e s 都可以表示成某些基础t a i l - b i t i n gt r e l l i s e s 的积( p r o d u c t ) 的形式。基于这个 结论，极小t a i l b i t i n gt r e l l i s e s 可以通过特征生成子( c h a r a c t e r i s t i cg e n e r a t o r s ) 来构 造。 群码( g r o u pc o d e s ) 与线性码相比，t a i l b i t i n gt r e l l i s e s 图更简单。v v a z i r a n i 等人把t r e l l i s 图从有限域上的线性码拓展到有限a b e l i a n 群上的群码。并给出 了一个高效的求解这种最小t r e l l i s 图的算法。 本文是在综合了上述结论后做出的。证明了有限交换群上线性码的t r e l l i s 也 具有与有限域上相同的一些性质，即群码的任意双真p 一基中向量的原子跨度与 非零首术元素的阶组成的集合是唯一的。 【关键词】：极小t r e l l i s ，t a j l b i t i n gt r e l l i s ，极小跨度形式，p 一基。 【中图分类号】：0 2 3 6 2 a b s t r a c t t h i st h e s i ss y s t e m a t i c a l l yd i s c u s s e st h et h e o r yo ft r e l l i sa n dt a i l b i t i n gt r e l l i s ，a n d g e n e r a l i z e ss o m ep r o p e r t i e so ft r e l l i sf o rl i n e a rc o d e so v e rf i n i t ef i e l d st of i n i t ea b e l i a n g r o u p s t r e l l i sp r o v i d e sa l le f f i c i e n tw a yt o i m p r o v et h ee f f e c t o fd e c o d i n gi nt h e c o m m u n i c a t i o n s y s t e m i tp l a y si m p o r t a n t r o l ei n e n c r y p t i o nt h e o r y a n d i n f o r m a t i o n & c o d i n gt h e o r y b yt h er u l eo fm a x i m u m l i k e l i h o o dd e c o d i n g ，v i t e r b i a l g o r i t h mo nt r e l l i sg r a p h sc a nb ee x e c u t e di no r d e rt od e c o d ec o d e se f f i c i e n t l y t h e r e f o r , t h ec o r ep r o b l e mo ft r e l l i st h e o r yi sh o wt oc o n s t r u c tt h es i m p l e s tt r e l l i s ， n a m e l y , m i n i m a lt r e l l i s m i n i m a ic o n v e n t i o n a lt r e l l i sf o rl i n e a rc o d e sc a nb eo b t a i n e df r o mt h ec o d e s g e r e r a t o rm a t r i xo rp a r i t ym a t r i x ，t h a ti s ，f r o mab a s i si nm i n i m a l - s p a nf o r m ， f u r t h e r m o r e ，t h es e to fs p a n so ft h ev e c t o r si nt h eb a s i si su n i q u e s o m ee x a m p l e s h a v es h o wt h a tt h ec o m p l e x i t yo ft a i l - b i t i n gt r e l l i s e sc a nb el o w e rt h a nt h eb e s t c o n v e n t i o n a lt r e l l i s ，s oi tc a l ll e a dt oam o r ee f f i c i e n td e c o d i n gm e t h o d t h eg e r e r a l m i n i m a lt a i l b i t i n gi ss t i l lao p e np r o b l e m ，b u tt ol i n e a rt a i l - b i t i n gt r e l l i si ti sf o l l o w e d t h a t ：a n yl i n e a rt a i l - b i t i n gt r e l l i sf o rl i n e a rc o d e sc a nb ee x p r e s s e da sap r o d u c to f s o m ee l e m e n t a r yt a i l b i t i n gt r e l l i s e s ，w h i c hl e a d st oa l l i m p o r t a n t r e s u l tt h a ti s m i n i m a lt a i l b i t i n gt r e l l i sf o rl i n e a rc o d e si sa p r o d u c to fs o m ec h a r a c t e r i s t i c g e n e r a t o r s t a i l b i t i n g t r e l l i s g r a p h f o r g r o u pc o d e s i s s i m p l e rt h a nf o r l i n e a rc o d e s v v a z i r a n ia n do t h e r se x t e n dt r e l l i sg r a p hf r o ml i n e a rc o d e so v e rf i n i t ef i e l d st o g r o u p sc o d e so v e rf i n i t ea b e l i a ng r o u p s ，a n dg i v ea ne f f i c i e n ta l g o r i t h mt od e c o d et h i s k i n d0 f t r e l l j s a f t e rc o n c l u d i n gt h ea b o v er e s u l t s ，w ep r o v et h a tf o ra n yb i p r o p e rp - b a s i so fa g r o u pc o d e ，t h e i ra t o m i cs p a n sa n do r d e r so ft h ef i r s ta n dl a s tn o n z e r oc o m p o n e n t so f v e c t o r si nt h eb i p r o p e rp - b a s i sa r eu n i q u e a tl a s t ，w ed i s c u s st h ed i f f i c u l t i e sw h e n g e n e r a l i z et h es i m i l a rp r o p e r t yt ot a i l b i t i n gt r e l l i s e s k e yw o r d s ：m i n i m a lt r e l l i s ，t a i l b i t i n gt r e l l i s ，m i n i m a ls p a nf o r m ，p - b a s i s c h i n e s el i b r a r yc l a s s i f i c a t i o n ：0 2 3 6 2 4 第一章前言 t r e l l i s 最初是在有限状态自动机的研究中被引入的。在t r e l l i s 理论最初的二 十年问，它主要应用于卷积码的研究。近些年的研究专注于t r e l l i s 图在密码学和 信息论编码论领域的应用。格论的两个中心问题是最近向量问题( c v p ) 与最短向 量问题( s v p ) ，这两个问题是n p 一难的。基于格的公钥密码体制一般都是建立在 c v p 的难解性的基础上的。目前解决c v p 的一个重要方法是t r e l l i s 图，即先尽 可能建立格的一个简单的t r e l l i s 图，再利用v i t e r b i 算法来解c v p 。 t r e l l i s 图不但能很好地表示码的结构而且还能产生效率非常高的译码算法。 编码理论的核心在译码，编码方法是简单的，快速且耗费低廉的译码方法是通信 的关键所在。t r e l l i s 图与v i t e r b i 译码算法有天然的联系。利用t r e l l i s 图可以方便 地进行v i t e r b i 译码【1 】，而这种译码算法的复杂度是线性的。所以，问题的关键 就转化为怎么样构造极小t r e l l i s 图。遗憾的是这个问题对非线性码可能是n p 难 问题【3 】，而对于线性码已经得到了很好的解决。d j m u d e r 在【6 】提出了一种构造 分组码的极小真t r e l l i s 的方法，并证明了线性码的任意极小真常规t r e l l i s 都是同 构的。此外有很多种方法构造线性码的极小常规t r e l l i s ，比如b c j r 构造 7 】、 k s c h i s c h a n g 和s o r o k i n e 构造【3 】等。这些看似不同的t r e l l i s 图其实是同构的。 t a i l b i t i n g t r e l l i s 是一种在常规t r e l l i s 的基础上改进的t r e l l i s 。它的时问轴( t i m e a x i s ) 的拓扑结构构成环状而不是常规t r e l l i s 的区间。通过一些例证已经知道， t a i l b i t i n g t r e l l i s 的复杂度比最好的常规t r e l l i s 要低，在 5 1 ，【8 】证明了一个线性码 的t a i l b i t i n gt r e l l i s 图的状态数与常规t r e l l i s 的相比是平方根的关系。 k s c h i s c h a n g 和s o r o k i n e 3 对分组码的极小t r e l l i s 进行了研究，证明了线性 码的常规t r e l l i s 可由极小跨度形式的基生成，并且原子码的跨度集台一定是唯一 的。k o e t t e r 和v a r d y l 4 证明了极小线性t a i l b i t i n gt r e l l i s 可以通过特征生成子来 构造。v a z i r a n i 等人在文献1 1 4 1 对群码上的常规t r e l l i s 的性质做了积极的探讨， 对有限域上线性码的t r e l l i s 进行了扩展。他们定义了在有限交换群上讨论t r e l l i s 理论需要的一系列新概念。本文利用这些新概念，把k s c h i s c h a n g 和s o r o k i n e 对 常规t r e l l i s 研究的结论成功地由有限域推广到环z 一。，结果很完美；并试图将 k o e t t e r 和v a r d y 对t a i l - b i t i n gt r e l l i s 的结果推广到有限交换群上，对他们的个关 键定理进行重新考虑，计划未来可以做出更好的结果。 以下章节是这样安排的。第二章，对常规t r e l l i s 的基本概念做了介绍。一般 分组码存在同构意义上唯一的真t r e l l i s ，这个结论对于线性码或非线性码都是成 立的。但若不是真t r e l l i s 则没有这么好的结论。讨论了构建非线性码的一般t r e l l i s 时的困难。对于线性码，由于线性码本身良好的性质，这个方向的理论很完善。 线性码的常规t r e l l i s 可由极小跨度形式的基生成，并且原子码的跨度集合是唯一 的，线性码的极小常规t r e l l i s 是同构意义唯一的。 第三章重点讨论了t a i l - b i t i n gt r e l l i s 的理论。涉及基本概念以及它和常规 t r e l l i s 的许多不同点。然后重点讨论了线性t r e l l i s 理论，以及线性极小t a i l - b i t i n g t r e l l i s 的构造方法：即若干特征生成子做积操作。 第四章首先讲述了t r e l l i s 理论在有限交换群上的扩展。说明了系列定义：包 括p 一线性组合，p - 生成子序列，p - 线性无关，p 一基础，双真p 一基等等。这些新概 念是进行新工作的重要工具。然后本文提出了新的结论：在环z 。上，t r e l l i sp 基的原子跨度与向量首末非零元素的阶组成的集合是唯一的。注意到有限域上非 零元素的阶是一致的，当取z 。为有限域时这个结论就弱化为k s c h i s c h a n g 和 s o r o k i n e 证明过的结论。所以这个结果是对有限域上原子跨度相应性质的完美推 广。另外，本文试图将极小线性t a i l b i t i n gt r e l l i s 的构造方法也推广到环z 。，这 个工作已经开了头，在文章的最后对这个工作的困难做了一些分析。 第二章常规t r e l l i s 这一章讲述常规t r e l l i s 的性质，包括一般分组码、非线性码和线性码的内容。 2 1 基本概念及t r e i iis 的译码 一个边标记的有向图称为常规t r e l l i s ，它表示一个三元组( y ，e ，a ) ，y 是节 点的集合，e 是边的集合，每条边表示成( ，1 2 ，y 。) ，其中 ，y 。e v ，ae a 。集合 a 是字母表。t r e l l i s 图当然属于一般图论意义上的图，但它有其自身的特点。矿 划分成n 个子集合v o ，v 1 ，k 1 在研究极小t r e l l i s 时，总是假定里有唯一的 点，称为起点，出度为1 ，k 。里有唯一的点v 。，称为终点，入度为1 。此外， 所有节点都有度数为1 的入度和出度。任意点v 都至少有一条从v 。开始的路径， 且如果这条路径上有m 条边，则v 的深度就是m 。下面是正式的定义： 定义2 1 1 常规t r e l l i st = ( e ，a ) 是一个深度为n 的边标记有向图，并且 具有下面的性质：点集y 被划分成矿= v o u k u u 吒。t 的每一条边始于k 终 于k 。，f = o , 1 ，一，n 一1 。 集合，k k 称为t 的点类( v e r t e xc l a s s e s ) 。有序索引集i = 0 ，l ，n 称为r 的基于点集y 划分的时间轴( t i m ea x i s ) 。点集y 的划分导致了边集类似的划分， 即e e lu e ：u u e 。，e ；是所有终结于k 中点的边的集合。当a 取有限域e ， 称丁是有限域e 上的t r e l l i s 。 下面介绍几种特殊的t r e l l i s 。 定义2 1 2 如果t r e l l i st 中所有从起点到终点的路径的边标记都不相同称t 是一对一的，或者称作可观察的( o b s e r v a b l e ) 。 定义2 1 3t r e l l i s t 是真的( p r o p e r ) 如果只有一个起始点v 。，并且所有始于 长度为i 的路径都有不同的边标记，i = 1 2 n 。 定义2 1 4t r e l l i s t 是补真的( c o p r o p e r ) 如果只有一个终点v 。，并且所有终 于任意节点的路径都有不同的边标记，i = 1 2 ，n 。 定义2 1 5t r e l l i st 是双真的( b i p r o p e f ) 如果r 既是真的又补真的。 从定义不难看出，可观察的t r e l l i s 是最弱的一类，因为它只要求每整条路 径的边标记互不相同，而真t r e l l i s 条件更加严格，它要求开始于相同点的每个边 标记都不相同。双真t r e l l i s 是最严格的，因为它要求不仅为真而且补真。几个具 体的例子见图2 1 1 。 ( a ) 不可观察( b ) 非真，但可观察 ( c ) 真，非补真 图2 1 1 ( d ) 双真 给定t r e l l i s t ，任意边q e e f ，存在标记a c a 以及点v f - 1 k l ，v i k ，使得 e ；= o 。，q ，a ) 。这样到v 。的每一条有向路径都会得到一条长度为n 的边标记 0 ，a ：，a 。) ，如果所有这样的边标记能够组成基于4 的分组码c 的所有码字， 就称t r e l l i st 表示的分组码c ，表示成c 口) 。这样就在t r e l l i s 图和分组码之间建 立了联系，从而可以用t r e l l i s 来表达分组码的构造。一般来讲，t r e l l i st 有比c 口) 的码字更多的标记路径，但对于可观察的t r e l l i s ，码字和标记路径是一一对应的。 在本文中所涉及的t r e l l i s 都是可观察的。 给定两个t r e l l i s t 和r ，如果存在一一映射妒：v v ，使得( v 。v ，n ) 当 且仅当( 妒0 1 ) ，妒( v 2 ) ，a ) e ，则称t r e l l i s t 和r 同构。显然，同构的t r e l l i s 保持点 集和边集的划分关系。同构的t r e l l i s 所表示的分组码有什么关系呢? 如果同构， 显然它们表示相同的码，反之则不然，即相同的分组码对应的t r e l l i s 可能不同构。 例如图2 1 2 所示，t r e l l i s 五和l 都表示分组码c = o l o ，1 0 0 ，1 0 1 ，1 1 1 ，但显然它 们不同构。 a ) l 图2 1 2 8 1 b ) t 2 那么对于同一个码，什么样的t r e l l i s 才是“最好”的t r e l l i s 呢? 首先要了解 t r e l l i s 在分组码译码过程中的作用。因此要了解v i t e r b i 算法【1 】，它是一个简单 的动态规划算法，从历史上看它促使了t r e l l i s 的诞生，并成为t r e l l i s 理论不可分 割的一部分。 定义2 1 6 t r e l l i s tu ( y ，e ，爿) ，令p = e ie 2 ，e 。是一条边标记路径，定义这 条路径上的流量为边标记的乘积，即p ( p ) = a ( e ，) a ( e ：) a ( e ，) 。两点问的流量 定义为这两点问所有路径的流量的和。 上述定义中的乘积运算满足拟群，) ，加法运算满足可交换半群即，+ ) 。即 似，+ ，) 是半环。v i t e r b i 算法实际上是计算两点间流量和的有力工具，赋予流量以 及加法乘法不同的具体含义，v i t e r b i 算法得出的结果就会有不同的意义。一般意 义的v i t e r b i 算法描述如下： 弘代表定义在边上的流量，0 ) 表示边e 的起点，z 0 ) 表示边e 的终点。庐是 t r e l l i s 的始点，妒是终点。表示空字符。 肛( ) 暑1 f o rf t lt o l ld o f o rv 矿d o ( v ) = 。( 。) ，( ，( 已) ) 。口( 已) ) r e t u r n 口( 妒) 可见，适合v i t e r b i 算法的实例具有”乘积的和”这样的形式。对t r e l l i s 进行 解码采用极大似然译码的原则，为了适应v i t e r b i 算法要求的形式，这里对极大 似然译码在形式上做一下修改。 假定通信信道是离散无记忆的。输入字符集x = 兄，输出字符集是y ，传 输概率函数，( i z ) ：y 一【0 ，1 】，其中x c x 。若输出端收到向量y ；( y l , y ：，y 。) ， 根据极大似然译码的原则，要找到使p r ciy 最大的码字c ，也就是找寻使概率 p r ylc 最大化的码字c 。将p r ylc 分解到各个分量， p r 2 珥p r 川c r 2 珥f y i ic i ) 取对数运算，并置结果于负号，得到， m a x 科n yl c ) = m n 耐善一1 。gf ( y ric r ) 欲最大化p r yic ) 就是要最小化上式等号右侧。而且这样的形势符合v i t e r b i 算法要求的”乘积的和”的，注意，这里”乘”是通常意义的加法，”和”是取小值操 作。给定一个t r e l l i s ，对的标记修改如下：如果有j 2 l e e e i1 a ( e 1 是边p 的标记 ( a ( e ) 的意义是传输这个边的概率) 。现在重新给它一个标记 c t ( p ) = 一l o g f ( y ，i a 0 ) ) ，于是， 砒斌善山g f ( y 小r ) = m i n q ，：，气净呻妒 a ( p 1 ) + 口e 2 ) + + a ( p ) ) ， 求得从起点到终点妒的上式的最小值就等于找到了极大似然译码的概率 值，取的这个值的n 条路径就表示应该译出的码字。 下面是v i t e r b i 算法的一个示例，给定的t r e l l i s 如下图所示： v 0 v 1 31 _ 2v 2 2 图2 1 3 肛( v 1 1 ) ；p p o ) + 1 2 0z1 2 0 p o l 2 ) = ( v o ) + o 2 5 = 0 2 5 肛( v n ) = “( v o ) + 1 。0 1 = 1 0 1 p ( v 2 1 ) = m i n ( ( v 1 1 ) + 0 1 2 ，( 1 2 ) + 0 3 2 ) = r a i n ( 1 3 2 ，0 5 7 ) = o 5 7 ( v 2 2 ) = m i n ( ( v 1 2 ) + 0 9 9 ，卢( 1 3 ) + 1 2 ) = r a i n ( 1 2 4 ，2 2 1 ) = 1 2 4 p 3 ) ，m i n ( f l ( v 2 1 ) + 0 7 9 ，m ( 2 2 ) + o 2 9 ) = m i n ( 1 3 6 ，1 5 3 ) ；1 3 6 求得最小值1 3 6 ，相应的路径是v 。，v 。：，v ：，p ，因此应该把这条路径对应的 码字作为译码。 定理2 1 1 【l 】t r e l l i st 一，e ，爿) 上的v i t e r b i 算法需要执行l 1 次乘法， i e l l 矿l + 1 次力日法。 具体证明见文献【1 】。可见v i t e r b i 算法的计算量直接基于在t r e l l i s 点( 或边) 的数量，为此简化译码的复杂度就要使t r e l l i s 的点集( 或边集) 最小。下面讨论 满足这个条件的极小t r e l l i s 。 设码c 是有限域f 2 上码长为n 的分组码，t r e l l i st = ，e ，2 ) 表示码c ， 有序序列o f ) ；( 1 k i ，l 1 ) - ， k 一，i ) 定义为f 的点参数类。码c 对应多个t r e l l i s ， 这些t r e l l i s 的点参数类组成元素间可比较的偏序集合。某个丁小于等于另一个r 。 记为t s t ，如果 i k l s i k 。i ， 其中i 一0 ，1 ，n 一1 。 如果等号不是总成立，记为l kl l k i ，称t 小于t 。 r k o e t t e r 和a v a r d y 在【4 】中详细说明了多种描述t r e l l i s 复杂度的方法，除 了上面的外，还有点类积序和点类最大序。具体的含义是： 丁s i - i 丁如果y l o li s i ：i 暇i ts 。t 。如果m a x 川ki ) 5 m a x ；( i k 1 ) ， 同样的，可以定义基于以上两种排序的极小t r e l l i s 。根据定义，容易看出如 零在5 e 意义! 曼j 、掣譬然在；耳和e 意义下也最小。如果在s 兀意义下最 小则i 仕- - h - s 通、常也最小，但不总是成立。m a x 参照以上排序规则可定义多种极小t r e l l i s 。本文采用s 。序下的定义： 定义2 1 7 基于点参数类的极小t r e l l i s t 定义为：如果不存在丁。，丁+ c 丁，则 称t 是极小的。 极小t r e l l i s 是t r e l l i s 理论的中心问题。对于非真t r e l l i s ，如果是线性码的t r e l l i s 那么这个问题研究得比较透彻，并已有非常成熟的结论：如果是非线性码难度就 大得多，实际上，此时的极小t r e l l i s 甚至不是可观察的。对于真t r e l l i s ，这个问 题有非常好的答案，在下面给出主要的结论和方法，是由m u d e r 在【6 】做出的工 作。 2 2 分组码的极小真t r e i iis m u d e r 对分组码的极小常规t r e l l i s 作了丌创性的工作，证明了：任意分组码 都有极小真t r e l l i s ，且相同码的极小真t r e l l i s 都是同构的。定理的证明读者可以 参看【6 】。下面，遵循这个定理的思路介绍分组码的常规t r e l l i s 的基本知识。 令c 是有限域f 上长度为n 的分组码，定义两个集合： p l = ( c 1 ，c 2 ，e j ) ：( c l ，c 。，c j + 1 ，c 。) e c ，3 c m ，c 。， ，i 一0 ，n 一1 称作 码字c 的首部集合。它表示对于分组码c 所有码字的首部( c ，c ；) 的集合。当 i = n 时，显然巧l c 。 在t r e l l i s t 上考虑类似的问题。按照前面的定义，t 的点集划分为y = u z , u u k ，设v i k ，那么如果r 的两条路径相交于v i ，这两条路径分 别表示码字c ，c 。，那么称为一等价，记为c ，c ，表示对应的路径终止于相同的 节点。t - 等价对于真t r e l l i s 是个等价关系，很容易验证它满足自反，对称和传递i 但对于非真t r e l l i s 就不再是等价关系，如下图所示，1 1 ，0 1 ，0 0 ，但1 1 和0 0 不 是t 等价。 0 l 图2 2 1 下面要定义另一种等价关系。任意e 只，称c 的未来为下面的公式： f ( c ) - 缸c a ”：( c 工) c ) ，点运算表示字符串连接，彳是t r e l l i s 的字符集，简 单地，可以取有限域。定义由只引导的“未来等价”关系：c ，c p + ，如果 f ( c ) = f ( c ) ，称c 和c 未来等价，记为c c 。它们有相同的尾部。 未来等价关系是基于t _ 等价关系一，的，即考察的对象是c 只+ 的尾部 f ( c ) ，如果它们相等就称它们未来等价。这点从定义中可以看出，也是以下定 理的要点。 引理2 2 2 1 6 设丁是分组码c 的真t r e l l i s ，那么对于任意的c ，c 。p ，如果 t _ 等价必然未来等价。 证明是明显的，这里只做说明：c ，c 终止于同一点，它们的尾部自然相等。 设lk + i 表示在p i 中由未来一等价关系确定的等价类的数量。 定理2 2 3 【6 】设r 是分组码c 的真t r e l l i s ，v = u _ u u 一。是t r e l l i s 的点集划分，有结论，l kl 爿+ i ，其中i zo ，1 ，n 。 根据引理2 2 2 ，由未来等价关系确定的等价关系类的数量不可能超过由 t - 等价类确定的等价关系类的量，所以这个定理成立。这个定理很具有启发性， 根据它，可以想象如果某个t r e l l i s 以k + 作为点集，那么它是最小的。也就是说， t r e l l i s 的任意点集k 的大小都不会比k 小，i = o ，1 ，n 。 根据以上分析可以构造极小真t r e l l i s 。当i = 0 , 1 ，n ，令k + 表示基于p i 的由 未来一篝价关系确定的等价类，显然巧一中，= c ，略，0 都只含有一个元素。 设y ；巧u v , + u u v , 为分组码c 的极小真t r e l l i st 一+ ，e ，s ) 的点集。边 集e + 定义如下：如果点v k 到点v ：，有边，当且仅当边标记 ( c 1 ，c 2 ，c 。) e c ，其中( c 1 ，c 2 ，c f ) v 和( c 1 ，c 2 ，c ) e v 。，这个边就标记为c i + 1 ， 当然，c l + 1 e a 。 下面举简单的例子说明这种构造t r e l l i s 的方法。 一 k + ， a ) c ) 图2 2 2 图2 2 2a ) 中i 1 1 3 ，i k + ，i - - 2 。v i 中的上面两个节点是t - 等价的，据引理 2 2 2 它们也是未来一等价的，因此可以合并成一个节点从而得到j k i ，它有两个 等价类，如图2 2 2b ) ，显然k 节点数小一些。 设分组码c = 0 0 0 ，1 0 0 ，1 0 1 ，1 1 1 ，在i = 1 和i ；2 时有，p 1 = o ) u m ， 巧z 0 0 ) u 1 0 u 1 1 ，得到的t r e l l i s 表示如图2 2 2c ) 所示。在这个例子中会不 会出现下面的问题呢? p ；中，0 0 和1 0 都有结束于0 的码字，那么是不是应该把 它们合并，并得到图2 , 2 2d ) 1 1 j d ? 图2 2 2d ) 的t r e l l i s 显然比图2 2 2c ) 在 。意义 上更小。但答案是不能。直接的解释是1 0 不但有码字1 0 0 还有另外的码字1 0 1 ， 1 0 和0 0 不会未来等价，而且图2 2 2d ) 的t r e l l i s 比原本的码c 多出了一个码字 0 0 1 ，因此它甚至谈不上是代表码c 的t r e l l i s 。更普遍的原因是下面的引理： 引理2 2 4 在新构成t r e l l i st 中不会出现下图所示的情况： 图2 2 3 这里c ，c ：，因此c 。c ：，所以在构造丁+ 的步骤里c ，和c ：不会出现交叉在 一起的情况，即图2 2 3 不可能出现的。用刚才的例子来讲，o o 和1 0 不会交叉 到一起，这样得到的t r e l l i s 就不会是图2 2 2d 1 那样了。口 定理2 2 5 【6 】由上面的方法确定的t r e l l i st 是分组码的极小真t r e l l i s 。 证明：完整的证明件参考文献【6 】，这里只提到使用引理2 2 4 的部分。 首先证明丁+ 是真t r e l l i s 。反设丁存在两条始自相同点但边标记不同的边， 设为e l = ( v ，v ，a ) f f l e ：= v ，v ”，a ) ，其中v k 。依照这个假设，又根据丁的构造 方法，势必存在c 的两个码字c ，c 。使得c 一( c ，c ：，c i ) 终结于p ，c ( e l ，c 2 ，c ：) 也终结于v ，并且( c 。，c ：，c ；，c 。) 终结于v 。，( c ：，c ：，c ：，c ；+ 。) 终结于v ”，这里 c l + ，= c 。= a 。如下图所示： 图2 2 4 实际上，由引理2 2 4 ，图2 2 4 所示情况是不可能出现的。所以丁+ 是真的。 接下来要证明r 。确实表示码c ，剩下的证明过程参考文献【6 】。 口 文献【6 】进一步证明了“一个重要结论：分组码c 的所有极小真t r e l l i s 都同构 于丁+ 。因此对于任意的分组码，都有同构意义上唯一的极小真t r e l l i s 。只要是分 组码则不管是线性码还是非线性码都满足这个定理，这是一个很强的结果。现在 回忆一下这个极小真t r e l l i s t 是怎么得来的。首先，它的极小性由定理2 2 3 保 证；它确实是一个真t r e l l i s ，这由引理2 2 2 可以得到；它的点集是未来等价关系 确定的矿+ ，边集是e ，在前面提及；按照未来等价关系对各个点集进行化简就 得到了r + 。 2 3 非线性码t r e | iis 的讨论 对于线性码，已经有很好的结论表明一定存在同构意义上唯一的线性t r e l l i s 这将在本文的后面部分论述，这一节只是针对非线性码。非真t r e l l i s 研究得比较 少，虽然它可能拥有比真t r e l l i s 更少的点，但是没有普遍的可行方法去获得复杂 度这样低的非真t r e l l i s 。实际上，这是一个n p 难问题。通过一个问题的等价转 换，我们将看到这一点。 给定时间点i , 0 c fc n ，任意码字c = ( c ，c ：，c 。) 都可以分为两部分：首部 和尾部，即首部鼻一( c ) = ( c ，c 。) ，尾部鼻+ ( c ) = ( c 。，c 。) 。前者是i 元组，后 者是n i 元组。按照这种方法处理分组码c 的所有码字，就形成了关于码c 在时 间点f 的两个集合只一( c ) = 只一( c ) ：c c ) 和e + ( c ) = e + ( c ) ：c e c ) 。作迪卡尔乘 积，显然有c 鼻一( c ) x e + ( c ) ，码c 可看成是首部和尾部构成的二元组的集合， 或者说是首部和尾部构成的二元关系，c = ( p ，) c 当且仅当( p ，) 符合这个关 系。 在码c t r e l l i s 的点集划分k 里取一点v ，把上面介绍的尾部首部的概念在v 点展开，得到了集合p ( v ) 和f ( v ) 。它们表示联接于v 点的所有码字的首部和尾部。 迪卡尔乘积尸( v ) f ( v ) 是二元关系c 的子集。见下图： 图2 3 1 e ( v n ) f ( v 。i ) e ( v 。2 ) f ( v 。：) 因为t r e l l i s 所有路径必然要经过时问点为i 的点集划分k ，所以当取遍k 的 点时，我们就得到所有的码字，也就得到码c 。也可以说，码c 是集合 妒( p ) f ( v ) ：v k ) 的并集。也就是下面这个式子： c = u 。( 尸( v ) f ( v ) ) 下面的图更加突出地表现了p ( v ) ，f ( v ) 和i ki 之间的关系，以及怎样把问题转 换到一个n p c 问题。 1 0 01 图a )图b ) 图2 3 2 分组码t o o ，1 0 ，1 1 是非线性码。图2 3 2 a ) 的行标识“1 ，0 ”代表码字的 首部p ，列标识“0 ，1 ”代表码字的尾部r 。码c 是首部和尾部的二元关系 ( p ( v ) ，f o ) ) 的集合。码字c e c 当且仅当0 ，f ) c c ，也就是在图中，相应格子里 存在一个黑点。比如， 0 1 1 不是c 的码字，而 t o ，1 1 ，0 0 1 都是c 的码字。图 2 3 2b ) 是2 3 2a ) 的另一种表示方法，即( p ，) c 当且仅当在p _ 手，间有线连接。 欲最小化l kl ，在图2 3 2a ) 中表现为寻找最小的矩阵形覆盖，去覆盖图中 的0 ，) 对。注意，这里的矩阵形覆盖是指，假设被覆盖元素有( n ，c ) ，( a , d ) ，p ，e ) 则一定有( n ，c ) 也被覆盖。从直观上看，覆盖的形状一定是一个矩形，不会有凹 陷或凸出形状出现。在图2 3 2b ) 中，表现为寻找最少的完全二分子图去覆盖图 中的边。注意，这里的完全二分子图恰恰体现了上面提到的矩阵形覆盖。因为如 果在图2 3 2a ) 中覆盖的是点，在图2 3 2b ) 就对应为覆盖边，如果在图2 3 2a 1 中的覆盖是矩阵形的则对应到图2 3 2b ) 就是用完全二分图去覆盖边。关于这些 图论的基本概念请参看文献【1 0 】。 这样，寻求t r e l l i s 的i ki 最小，就转化为以下问题： 给定二分图g = ( v ，e ) ，正整数ke l e i ，是否有v 的ksk 个子集 嵋，哆，k ，使每个k 诱导出一个g 的完全二分子图，并使得对每一条边 仁，v e ，总有某个包含“和v ? 在参考文献 1 1 中，我们知道这个问题属于n p c 类，除非p = n p ，否则是不 存在多项式时间算法的。真t r e l l i s 与非真t r e l l i s 的区别类似于确定型有限自动机 1 6 和非确定性有限自动机的区别。t r e l l i s 的一点v ，如果它有多条始白它的边并且 这些边拥有相同的边标记，在自动机理论中这就好比给定一个状态和输入符号非 确定型自动机拥有多个不确定的下一状态。自动机在读它的输入串时，每一步可 以选择转移到这些合法的下一个状态中的任一个。有关自动机理论的更多描述请 参看文献 1 2 。 在文献 3 e p ，k s c h i s c h a n g 和s o r o k i n e 总结了非线性码t r e l l i s 面临的其它一 些难点，具体的例子请参考文献 3 。概要归纳如下： 首先，我们寻找非线性码的极小t r e l l i s ，希望得到一个唯一的极小的t r e l l i s ， 但下面的例子表明，对于一个象码长为2 的二元码这样简单的非线性码，这样的 唯一性都不能得到满足。 其次，比非真更加弱的一个条件是不可观察的。从上一节的论述可知如果 不可观察就更不用说非真了。而非线性码的极小t r e l l i s 有时甚至连可观察这一基 本要求都达不到。 进一步的例子表明某些非线性码的极小t r e l l i s 也许根本就不存在。 总而言之，目前没有有效的手段找寻一般的非线性码的极小t r e l l i s 。情况对 线性码就乐观得多。线性码本质上是建立在生成矩阵之上的线性空间，现有的数 学理论为它的研究提供了良好的支持，所以，线性码的t r e l l i s 理论得到了很好的 发展，有。批非常积极的成果。我们在文章的剩余部分将把注意力放在对线性码 的讨