A flip-swap language is a set S of binary strings of length n such that S boolean OR {0(n)} is closed under two operations (when applicable): (1) Flip the leftmost 1;and (2) Swap the leftmost 1 with the bit to its rig...
详细信息
A flip-swap language is a set S of binary strings of length n such that S boolean OR {0(n)} is closed under two operations (when applicable): (1) Flip the leftmost 1;and (2) Swap the leftmost 1 with the bit to its right. Flip-swap languages model many combinatorial objects including necklaces, Lyndon words, prefix normal words, left factors of k-ary Dyck words, lattice paths with at most k flaws, and feasible solutions to 0-1 knapsack problems. We prove that any flip-swap language forms a cyclic 2-graycode when listed in binary reflected gray code (BRGC) order. Furthermore, a generic successor rule computes the next string when provided with a membership tester. The rule generates each string in the aforementioned flip-swap languages in O(n)-amortized per string, except for prefix normal words of length nwhich require O(n(1.864))-amortized per string. Our work generalizes results on necklaces and Lyndon words by Vajnovszki (2008) [35]. (c) 2022 Elsevier B.V. All rights reserved.
We first present a simple recursive algorithm that generates cyclic rotation graycodes for stamp foldings and semi-meanders, where consecutive strings differ by a stamp rotation. These are the first known graycodes ...
详细信息
We first present a simple recursive algorithm that generates cyclic rotation graycodes for stamp foldings and semi-meanders, where consecutive strings differ by a stamp rotation. These are the first known graycodes for stamp foldings and semi-meanders, and we thus solve an open problem posted by Sawada and Li (2012) [17]. We then introduce an iterative algorithm that generates the same rotation graycodes for stamp foldings and semi-meanders. Both the recursive and iterative algorithms generate stamp foldings and semi-meanders in constant amortized time and O(n)- amortized time per string respectively, using a linear amount of memory.
We present a simple algorithm that generates cyclic rotation graycodes for stamp foldings and semi-meanders, where consecutive strings differ by a stamp rotation. These are the first known graycodes for stamp foldin...
详细信息
ISBN:
(纸本)9783031343469;9783031343476
We present a simple algorithm that generates cyclic rotation graycodes for stamp foldings and semi-meanders, where consecutive strings differ by a stamp rotation. These are the first known graycodes for stamp foldings and semi-meanders, and we thus solve an open problem posted by Sawada and Li in [Electron. J. Comb. 19(2), 2012]. The algorithm generates each stamp folding and semi-meander in constant amortized time and O(n)-amortized time per string respectively, using a linear amount of memory.
We present a simple algorithm that generates a cyclic 2-graycode for ballot sequences. The algorithm generates each ballot sequence in constant amortized time using a linear amount of space. This is the first known c...
详细信息
We present a simple algorithm that generates a cyclic 2-graycode for ballot sequences. The algorithm generates each ballot sequence in constant amortized time using a linear amount of space. This is the first known cyclic 2-graycode for ballot sequences that achieves this time bound. In addition, the algorithm can be easily modified to output ballot sequences in binary reflected gray code order in constant amortized time per string using a linear amount of space.(c) 2022 Elsevier B.V. All rights reserved.
An asymptotically optimal trellis-coded modulation (TCM) encoder requires the joint design of the encoder and the binary labeling of the constellation. Since analytical approaches are unknown, the only available solut...
详细信息
An asymptotically optimal trellis-coded modulation (TCM) encoder requires the joint design of the encoder and the binary labeling of the constellation. Since analytical approaches are unknown, the only available solution is to perform an exhaustive search over the encoder and the labeling. For large constellation sizes and/or many encoder states, however, an exhaustive search is unfeasible. Traditional TCM designs overcome this problem by using a labeling that follows the set-partitioning principle and by performing an exhaustive search over the encoders. In this paper we study binary labelings for TCM and show how they can be grouped into classes, which considerably reduces the search space in a joint design. For 8-ary constellations, the number of different binary labelings that must be tested is reduced from 8! = 40320 to 240. For the particular case of an 8-ary pulse amplitude modulation constellation, this number is further reduced to 120 and for 8-ary phase shift keying to only 30. An algorithm to generate one labeling in each class is also introduced. Asymptotically optimal TCM encoders are tabulated which are up to 0.3 dB better than the previously best known encoders.
The optimal bit-wise demodulator for M-ary pulse amplitude modulation (PAM) over the additive white Gaussian noise channel is analyzed in terms of uncoded bit-error rate (BER). The BER analysis is based on studying th...
详细信息
The optimal bit-wise demodulator for M-ary pulse amplitude modulation (PAM) over the additive white Gaussian noise channel is analyzed in terms of uncoded bit-error rate (BER). The BER analysis is based on studying the bit patterns that form a labeling. New closed-form BER expressions for 4-PAM with any labeling are developed. Moreover, closed-form BER expressions for 11 out of 23 possible bit patterns for 8-PAM are presented, which enable us to obtain the BER for 8-PAM with some of the most popular labelings, including the binary reflected gray code and the natural binarycode. Numerical results show that, regardless of the labeling, there is no difference between the optimal demodulator and the symbol-wise demodulator for any BER of practical interest (below 0.1).
A graycode is an encoding of integers as sequences of bits with the property that the representations of adjacent integers differ in exactly one binary position. graycodes have many practical applications that go be...
详细信息
ISBN:
(纸本)9781467357586;9781467357593
A graycode is an encoding of integers as sequences of bits with the property that the representations of adjacent integers differ in exactly one binary position. graycodes have many practical applications that go beyond research interests. There are different types of graycodes: binaryreflected, Maximum Gap, Balanced, Antipodal and Non Composite to name a few. On the other hand Reversible logic has received great attention due to their ability to reduce the power dissipation--an important aspect of low power circuit design. Other applications include Optical information processing, DNA computing, bio informatics, quantum computation andnanotechnology. Counters have a primary function of producing a specified output sequence and are thus sometimes referred to as pattern generators. This paper proposes design of different graycode counters using reversible logic gates, to draw comparative conclusions upon their performance.
Recent results have shown that the performance of bit-interleaved coded modulation (BICM) using convolutional codes in nonfading channels can be significantly improved when the interleaver takes a trivial form (BICM-T...
详细信息
Recent results have shown that the performance of bit-interleaved coded modulation (BICM) using convolutional codes in nonfading channels can be significantly improved when the interleaver takes a trivial form (BICM-T), i.e., when it does not interleave the bits at all. In this paper, we give a formal explanation for these results and show that BICM-T is, in fact, the combination of a TCM transmitter and a BICM receiver. To predict the performance of BICM-T, a new type of distance spectrum for convolutional codes is introduced, analytical bounds based on this spectrum are developed, and asymptotic approximations are presented. It is shown that the free Hamming distance of the code is not the relevant optimization criterion for BICM-T. Asymptotically optimal convolutional codes for different constraint lengths are tabulated and BICM-T is shown to offer asymptotic gains of about 2 dB over traditional BICM designs based on random interleavers. The asymptotic gains over uncoded transmission are found to be the same as those obtained by Ungerboeck's one-dimensional trellis-coded modulation (1D-TCM), and therefore, in nonfading channels, BICM-T is shown to be as good as 1D-TCM.
In this paper we study the problem of the whole mirror duplication-random loss model in terms of pattern avoiding permutations. We prove that the class of permutations obtained with this model after a given number p o...
详细信息
In this paper we study the problem of the whole mirror duplication-random loss model in terms of pattern avoiding permutations. We prove that the class of permutations obtained with this model after a given number p of duplications of the identity is the class of permutations avoiding the alternating permutations of length 2(p) + 1. We also compute the number of duplications necessary and sufficient to obtain any permutation of length n. We provide two efficient algorithms to reconstitute a possible scenario of whole mirror duplications from identity to any permutation of length n. One of them uses the well-known binary reflected gray code (gray, 1953) [10]. Other relative models are also considered. (C) 2010 Elsevier B.V. All rights reserved.
Separability in a code is crucial for guaranteeing a decent separation between multiple classes in terms of Hamming distance. In biometric discretization, this property is of particular useful for preserving dissimila...
详细信息
ISBN:
(纸本)9781424450466
Separability in a code is crucial for guaranteeing a decent separation between multiple classes in terms of Hamming distance. In biometric discretization, this property is of particular useful for preserving dissimilarity in the continuous feature space when a feature is mapped to a code space. binary reflected gray code (BRGC), a widely employed output label in discretization schemes, however, does not appear to exhibit such a property, yielding an indefinite mapping process that impedes the overall recognition performance. This paper explores and analyzes the separability of BRGC and put forward a class of coding scheme which exhibits high separability capacity.
暂无评论