构建可变长度的平衡格雷码

169 浏览量更新于2024-08-27 收藏 492KB PDF 举报

"长度灵活的平衡格雷码" 这篇研究论文探讨了"长度灵活的平衡格雷码"，这是一种在数字通信和编码理论中具有重要应用的特殊二进制序列。平衡格雷码（Balanced Gray Code，BGC）是一种格雷码的变体，其特点是相邻两个码字之间的差异不超过一个比特，并且在整个码字序列中，每个比特位置的变化次数是相等的，从而达到良好的平衡性。这种特性使得平衡格雷码在信号转换、错误检测和编码解码等方面有着广泛的应用。论文指出，Robinson 和 Cohn 在先前的工作中构建了一个 (n+2)-bit 的平衡格雷码，该码字长度为 2n+2，基于一个 n-bit 的平衡格雷码。然而，这篇论文扩展了他们的构造方法，允许生成具有灵活长度的 (n+2)-bit 平衡格雷码。这个创新在于，通过从 n-bit 平衡格雷码的过渡序列中选择一个子序列来实现长度的灵活性。论文的作者 Lu Wang、Zulin Wang、Qin Huang 和 Mu Zhang 首先确定了对于任何目标长度，所期望子序列的长度范围以及每个比特位置在子序列中出现的次数。他们提出了两个约束条件：一是子序列的长度必须满足特定范围；二是子序列中每个比特位置的出现次数应保持平衡。通过这些约束，他们能够构建出满足条件的 (n+2)-bit 平衡格雷码。在介绍部分，论文定义了一个 n-bit 格雷码 Ln，由 c0 到 c2n-1 组成，其中 k（0≤k≤2n-1）表示在两个连续码字 ck 和 c(k+1) 之间变化的比特位置。假设没有丢失一般性，作者们可以自由地选择比特变化的位置。在后续的章节中，论文可能会深入讨论如何确定子序列的选择策略，以及如何保证所构造的码字序列在长度可变的同时保持平衡性和循环性。此外，还可能涉及到算法设计、性能分析以及实际应用中的优势。关键词：平衡格雷码，过渡序列，灵活长度，二进制序列，编码理论。

894 IEEE COMMUNICATIONS LETTERS, VOL. 20, NO. 5, MAY 2016

Balanced Gray Codes With Flexible Lengths

Lu Wang, Zulin Wang, Member, IEEE, Qin Huang, Member, IEEE, and Mu Zhang

Abstract—Robinson and Cohn constructed an (n + 2)-bit

balanced Gray code (BGC) of length 2

n+2

from an n-bit BGC.

This letter extends their construction to ﬂexible lengths by select-

ing a subsequence from transition sequence of an n-bit BGC. For

any target length, we ﬁrst derive the length range of the desired

subsequence and the occurrence of each bit position in this subse-

quence. Then, an (n + 2)-bit balanced Gray code of ﬂexible length

can be constructed by selecting a subsequence under the two above

constraints.

Index Terms—Balanced Gray codes, transition sequence, ﬂexi-

ble lengths.

I. INTRODUCTION

GRAY code [1] is a counting sequence in which two

successive codewords differ only i n one bit position. Let

 c

, c

, ··· , c

−1

be an n-bit Gray code. The code is

called cyclic if only one bit changes between c

and c

−1

Deﬁne s

where 0 ≤ k ≤ 2

− 1 as the bit transition posi-

tion, in which the bit changes, between c

and c

(k+1) modulo 2

Without loss of generality, we assume that c

is an all-zero

codeword. The Gray code is then determined by its transi-

tion sequence s

, where s

 s

, s

, ··· , s

−1

. Moreover,

the number of transitions in bit position i in an n-bit counting

sequence, denoted by TC

(i), is called the transition count of

bit position i. The transition count distribution of all bit posi-

tions, i.e.,

(

(0), TC

(1), ··· , TC

(n − 1)

)

, is deﬁned as

the transition count spectrum of the counting sequence.

The most commonly known Gray code is the binary reﬂected

Gray code (BRGC) proposed by Frank Gray in 1953 to reduce

the error rate in some pulse coded communication systems

[1]. Balanced Gray codes (BGCs) [2] are a subclass of Gray

codes. In general, the distribution of bit transitions for a BGC

is uniform (or almost uniform) among bit positions, i.e., the

difference between every two transition counts is less than

or equal to 2. A 4-bit BRGC and a 4-bit BGC along with

their transition sequences are given in Table I. The transition

count spectrums of the BRGC and the BGC are (8, 4, 2, 2) and

(4, 4, 4, 4), respectively. However, if the transition position is

Manuscript received July 23, 2015; revised November 11, 2015; accepted

November 11, 2015. Date of publication November 17, 2015; date of current

version May 6, 2016. This work was supported in part by the National Natural

Science Foundation of China under Grant 61471022 and Grant 61201156, in

part by the NSAF under Grant U1530117. The associate editor coordinating the

review of this letter and approving it for publication was Z. Ma. (Corresponding

author: Q. Huang.)

L. Wang, Q. Huang, and M. Zhang are with the School of Electronic and

Information Engineering, Beihang University, Beijing 100191, China (e-mail:

wanglu09@buaa.edu.cn; qinhuang@buaa.edu.cn; calering_ococ@163.com).

Z. Wang is with the School of Electronic and Information Engineering,

Beihang University, Beijing 100191, China, and also with the Collaborative

Innovation Center of Geospatial Technology, Wuhan 430079, China (e-mail:

wzulin@buaa.edu.cn).

Digital Object Identiﬁer 10.1109/LCOMM.2015.2501291

TABLE I

A4-B

IT BRGC, A 4-BIT BGC AND THEIR TRANSITION SEQUENCES

ignored between the last and the ﬁrst codeword, the spectrum

changes to (8, 4, 2, 1) for BRGC and (4, 4, 4, 3) for BGC.

BGCs have been used in many applications, such as

phase change memory (PCM) [3], M-ary phase shift keying

(PSK) [4], and DNA computing [5]. Robinson-Cohn construc-

tion [2] is a well-known method to construct binary BGCs,

which derives (n + 2)-bit BGCs from n-bit BGCs. Suparta and

Zanten developed a general version of Robinson-Cohn con-

struction in [6] and described the results in algebraic form. Bose

and Broeg [7], [8] introduced Lee distance into Gray codes.

Later, Flahive and Bose [9] constructed binary and non-binary

(R-ary) BGCs based on partition-blocks over Lee distance. For

example, when R = 4, binary BGCs can be designed with the

mapping 0 – 00, 1 – 01, 2 – 11, 3 – 10.

However, the existing BGC construction methods only pro-

duce codes with ﬁxed length, e.g., 2

for an n-bit binary BGC

and R

for an n-bit R-ary BGC. Therefore, in order to obtain

binary BGCs of ﬂexible lengths, we propose a generalized

Robinson-Cohn construction by selecting certain subsequences

from the transition sequence of an n-bit BGC. First, the length

range of the desired subsequence according to the target BGC

is computed. Then, the occurrence of each bit position in the

desired subsequences is derived. Given the length and bit posi-

tion occurrence, a subsequence to construct an (n + 2)-bit BGC

of desired length can be chosen. In some cases, the difference

between every two transition counts can be even less than or

equal to 1.

II. BGC

S WITH FIXED LENGTHS

In this section, we will brieﬂy introduce the algebraic form

of Robinson-Cohn construction [6].

Consider an n-bit cyclic Gray code L

whose transition

count spectrum is ( TC

(0), TC

(1), ··· , TC

(n − 1)).Let

See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

下载后可阅读完整内容，剩余3页未读，立即下载

weixin_38685173

粉丝: 5
资源: 923

构建可变长度的平衡格雷码

输入一个数n，输出从0到n的格雷码

生成格雷码图案matlab程序

geleima.rar_格雷码_格雷码C语言

GLM.rar_格雷码_格雷码生成

trellis.rar_trellis_卷积码 格雷码_格雷_格雷码

格雷码与反格雷码介绍及生成方式

格雷码问题 分治法产生n位的格雷码

glm.zip_existzpp_格雷码_格雷码换算

int2gray.rar_格雷码_格雷码生成

用于生产格雷码光轴编码器：将产生一个n位格雷码轴编码器的图形和一个格雷码表-matlab开发

最新资源

trellis.rar_trellis_卷积码格雷码_格雷_格雷码

格雷码问题分治法产生n位的格雷码