关于右完全码的一个问题.PDF

杭州师范学院学报(自然科学版) Vo l. 3 No. 2 第 3 卷第 2 期 2004 年 3 月 Journal of Hangzhou Teachers CollegeCNatural Science Edition) Mar. 2004 文章编号:1008←9403(2004)02一0085-02 关于右完全码的一个问题 夏华庆，沈传龙 (杭州师范学院数学系，浙江杭州 310012) 摘 要:主要解决了 M. Satyanarayana 在文[lJ 中提出的一个问题:证明若一个码 X 并#满足 A+ X~ XA+ ， 则 X 是一致码.同时给出了一个右完全码 X 满足 A 婪 X~XA椅的一些充要条件. 关键词:右完全码;一致码;信号码 中图分类号: 0152.7 文献标识码:A 右完全码在前缀码理论中占有很重要的地位，对右完全码的某些结构和性质的研究具有很大的意 义. M. Satyanarayana 在文[lJ 中讨论了右完全码的一些性质，并提出了两个问题.问题 1 :给出一个右完 1 全码 X 满足 A僻 XCXA铃或 A XCXA十的充要条件.问题 2 :证明或否定一个满足 A- XCXA+ 的码 X 是一致码.在此用巧妙而简捷的方法证明了一个码X 芋￠满足 A1X 豆 XA+ ， 则 X 是一致码.从而完全 解决了问题 2 ，同时还给出了与问题 I 相关的一些充要条件. 设 A 是一个符号的非空集合，叫做字母表.每个符号叫做字母.一个字母表 A 上的字是有限多个符号 的有序列.不含任何符号的字称为空字，用 1 表示.对任意宇 w 有 z叫 lw = w.A 上所有字的集合记做 A\A姊在连接运算下构成一个么半群.在A善中定义a]a …a = b]b …ba; ， bjEA 当且仅当 n m ， 矶= Z 2 b (i=1.2 , … , n) .A 骨成为一个自由么半群，记A+=A椅←{ 1).用 |ω| 表示的宇w 的长是指w 中字母的 j 个数. 定义 1 一个A才的子集X 叫做A 上的一个码，如果.1].12 ….1 = Y]Yz …y , ,.1; Y E X，则 n == m ,.Ii j Yj 对一切 l :S; i~二 n 成立. 定义 2 一个码 X 称为 A 上的一致码，如果 X = AP(户是正整数). 定义 3 一个码X 叫做 A 上的极大码，如果 Y 也是 A 上的一个码，且 XCY， 则 X=Y. 定义 4 X 上的自由子么半群记做X\在 X 中的字叫做码字，X‘中的字叫做信息.一个字 uEA祷， 叫做字 ω 的左(右)因子，如果对某个 uεA畴 ， uv = w(vu = w). 且如果 u 笋1，则称为真左(右)因子. 定义 5 一个码 X 称为右完全码，如果对每个 uεA\存在