DFT Domain Characterization of Quasi-Cyclic Codes

 The transform domain characterization of linear cyclic codes over finite fields using Discrete Fourier Transform (DFT) over an appropriate extension field is well known. In this paper, we extend this transform domain characterization for linear quasi-cyclic codes over finite fields. We show how one can derive a lower bound on the minimum Hamming distance of a quasi-cyclic code and decode the code upto that minimum Hamming distance using this characterization. Received: January 17, 2002; revised version: November 30, 2002 RID="*" ID="*" This work was partly supported by CSIR, India, through Research Grant (22(0298)/99/EMR-II) to B. S. Rajan Keywords: Quasi-cyclic codes, Discrete Fourier transform, Cyclotomic cosets. Part of this work was presented in ICCCD 2000, Kharagpur, India and ISIT 2001, Washington D.C., USA     

Resistor-logic demultiplexers for nanoelectronics based on constant-weight codes

The voltage margin of a resistor-logic demultiplexer can be improved significantly by basing its connection pattern on a constant-weight code. Each distinct code determines a unique demultiplexer, and therefore a large family of circuits is defined. We consider using these demultiplexers for building nanoscale crossbar memories, and determine the voltage margin of the memory system based on a particular code. We determine a purely code-theoretic criterion for selecting codes that will yield memories with large voltage margins, which is to minimize the ratio of the maximum to the minimum Hamming distance between distinct codewords. For the specific example of a 64 × 64 crossbar, we discuss what codes provide optimal performance for a memory.     

Error Control in Residue Number Systems

 This paper introduces an alternate approach to error control in residue number systems which utilizes sets of moduli that include pairs with non-trivial common factors. Necessary and sufficient conditions for achieving a specified capacity for error detection or correction are derived by considering the minimum Hamming distance of an associated linear code. Effective error-control procedures are developed based on a syndrome matrix whose entries are obtained directly from the residue digits. The potential of a priori bounds on the magnitude of measurement errors to increase the efficiency of the control process is analyzed. Received: January 12, 2001; revised version: June 25, 2002 Keywords: Residue number systems, Error correction, Error detection, Computational errors, Instrumentation errors, Transmission noise, Coding theory.     

Higher weights for codes over rings

A generalized definition of higher weights for codes over finite chain rings and principal ideal rings and bounds on the minimum higher weights in this setting are given. Using this we generalize the definition for higher MDS and MDR codes. Computationally, the higher weight enumerator of lifted Hamming and Simplex codes over \mathbbZ₄{\mathbb{Z}_4}, the minimum higher weights for the lifted code of the binary [8,4,4] self-dual extended Hamming code, the lifted code of the ternary [12,6,6] self-dual Golay code and the lifted code of the binary [24,12,8] self-dual Golay code are given. Joint weight enumerators are used to produce MacWilliams relations for specific higher weight enumerators.     

The synthesis of magnetic recording trellis codes with good hamming distance properties

In this paper we present, by means of an example, a systematic procedure to synthesize combined modulation/error correcting trellis codes, suitable for Viterbi decoding. This synthesis is based on firstly selecting a suitable linear convolutional code, secondly by analysing the state system of this code to determine the important Hamming distance building properties, and finally by mapping a code with the desired restrictions on its sequences onto this state system. As an example we develop a R = 3/6 dc free (b,l,c) = (0,3,2) code withd_{min} = 4. This code improves on the best codes in [1]. Codes havingb geq 1, and which will thus be more suitable for magnetic recording, can also be synthesized following the proposed procedure.     

Code design using deterministic annealing

We address the problem of designing codes for specific applications using deterministic annealing. Designing a block code over any finite dimensional space may be thought of as forming the corresponding number of clusters over the particular dimensional space. We have shown that the total distortion incurred in encoding a training set is related to the probability of correct reception over a symmetric channel. While conventional deterministic annealing make use of the Euclidean squared error distance measure, we have developed an algorithm that can be used for clustering with Hamming distance as the distance measure, which is required in the error correcting scenario.     

Frequency-hopping optical orthogonal codes with arbitrary time-blank patterns

We investigate a general scheme of frequency-hopping optical orthogonal codes with a specified distance between adjacent frequency symbols and propose a novel code that allows time blanks between adjacent frequency symbols in code sequences. A time blank represents the absence of frequency symbols in code sequences and makes no interference with frequency components. The insertion of time-blank patterns can provide ample scope to generate much more code sequences than the conventional codes lacking in time-blank patterns, and we show this by constructing an algorithm to generate the proposed code. The performance analysis demonstrates that its performance is superior to that of the conventional codes in terms of the bit error rate. We also derive the upper bound on the proposed code set.     

On codes over quaternion integers

Decoding algorithms for the correction of errors for cyclic codes over quaternion integers of quaternion Mannheim weight one up to two coordinates are discussed by Özen and Güzeltepe (Eur J Pure Appl Math 3(4):670–677, 2010). Though, Neto et al. (IEEE Trans Inf Theory 47(4):1514–1527, 2001) proposed decoding algorithms for the correction of errors of arbitrary Mannheim weight. In this study, we followed the procedures used by Neto et al. and suggest a decoding algorithm for an $n$ length cyclic code over quaternion integers to correct errors of quaternion Mannheim weight two up to two coordinates. Furthermore, we establish that; over quaternion integers, for a given $n$ length cyclic code there exist a cyclic code of length $2n-1$ . The decoding algorithms for the cyclic code of length $2n-1$ are given, which correct errors of quaternion Mannheim weight one and two. In addition, we show that the cyclic code of length $2n-1$ is maximum-distance separable (MDS) with respect to Hamming distance.     

Viterbi decoding and the power spectral densities of some rate one half binary DC free modulation codes

The Hamming distance properties are investigated, and some experimental results obtained with the following R = 1/2 binary dc free modulation codes are presented: the (b, l, C) = (1, 5, 3) Miller²code and codes with (b, l, C), respectively, (1, 4, 3), (0, 3, 3), and (0, 1, 2). A R = 3/6, (b, l, C) = (0, 3, 2) combined error-correcting/ modulation code is also investigated. State systems, power spectral densities, and the bit error rates after computer simulated decoding of these codes on both the binary symmetric channel and a burst erasure channel are presented.     

遥控起爆器的汉明码纠错应用研究

(8,4)汉明码易于遥控起爆器实现纠错功能,文章给出了其编译码算法,并采用CC1100无线模块对其性能进行了测试。测试结果表明,采用(8,4)汉明码,误码率最大降低了80%,遥控距离最大增加了近50%。(8,4)汉明码能有效降低遥控起爆的误码率,增加遥控距离,在遥控起爆器中具有很强的实用价值。     

On the Concatenated Structure of a Linear Code

We address here the problem of finding a concatenated structure in a linear code ? given by its generating matrix, that is, if ? is equivalent to the concatenation of an inner code B ₀ and an outer code E ₀, then find two codes B and E such that their concatenation is equivalent to ?. If the concatenated structure exists and is non trivial (i.e. the inner code B is non trivial), the dual distance of ? is equal to the dual distance of B. If this dual distance is small enough to allow the computation of many small weight words in the dual of ?, it is possible to recover first an inner code B, then an outer code E whose concatenation is equivalent to ?. These two codes are equivalent respectively to the original inner and outer codes B ₀ and E ₀.     

Reconsidering natural binary encoding for absolute positionmeasurement application

It is well known that absolute encoders using natural binary codes are prone to reading errors because more bits can change between adjacent scale sectors. Some solutions, such as V-scan, were proposed to solve this problem, but they required too many additional reading heads and decoding circuits to be competitive with the reduced complexity obtained when using the Gray code. The author describes a novel natural binary absolute encoder using an original scanning technique that solves more efficiently the problem of the inherent code reading errors. It is shown that for the same nominal resolution, the complexity of the encoder is similar to, if not better than, that of the Gray-type encoder     

1-Perfect Uniform and Distance Invariant Partitions

Let F ⁿ be the n-dimensional vector space over ℤ₂. A (binary) 1-perfect partition of F ⁿ is a partition of F ⁿ into (binary) perfect single error-correcting codes or 1-perfect codes. We define two metric properties for 1-perfect partitions: uniformity and distance invariance. Then we prove the equivalence between these properties and algebraic properties of the code (the class containing the zero vector). In this way, we characterize 1-perfect partitions obtained using 1-perfect translation invariant and not translation invariant propelinear codes. The search for examples of 1-perfect uniform but not distance invariant partitions enabled us to deduce a non-Abelian propelinear group structure for any Hamming code of length greater than 7. Received: March 6, 2000; revised version: November 30, 2000     

Rate 8/9 sliding block distance-enhancing code with stationarydetector

A new distance-enhancing code for partial-response magnetic recording channels eliminates most frequent errors, while keeping the two-step code trellis time invariant. Recently, published trellis codes either have lower code rates or result in time-varying trellises with a period of nine, thus requiring a higher complexity of detectors and code synchronization. The new code introduces dependency between code words in order to achieve the same coding constraints as the 8/9 time-varying maximum transition runlength (TMTR) code, with the same code rate, but resulting in a trellis that has a period of 2. This code has been applied to the E²PR4 and a 32-state generalized partial response (GPR) ISI target. The resulting two-step trellises have 14 and 28 states, respectively. Coding gain is demonstrated for both targets in additive white Gaussian noise     

IFS分形码的快速图像检索算法

图像经分形编码后产生IFS分形码，它可被用来进行图像检索操作。针对图像检索的特点，将分形码中的位置参数替换为相对距离与方向系数。定义了分形码间的距离以及图像间的分形码距离，并取出分形码距离最小的前门幅图像作为检索结果，由此提出了基于IFS分形码的快速图像检索算法。从时间复杂性上分析，利用本文算法所需的检索时间与值域块的个数有关。实验结果表明，相对缩放与旋转变化，算法对位移与亮度变化具有较强的稳定性，其分形码距离的均值仅为14.07和20．05；并可检索到具有一定相似性的图像，且类间与类内分形码距离约相差8，类内距离远小于类间距离。     

Generalized quasi-cyclic codes: structural properties and code construction

Generalized quasi-cyclic (GQC) codes are defined by generator matrices comprised of circulant matrices of lengths not necessarily identical. A decomposition of these codes is given by using the Chinese reminder theorem. The focus is to characterize ρ-generator GQC codes in details. A good lower bound on the minimum distance of such a code in terms of the minimum distance of the constituent codes is given. Construction methods are given and a set of GQC codes is provided that from minimum distance perspective are optimal codes among the known linear codes having the same length and dimension.     

A SEU-protected cache memory-based on variable associativity of sets

SRAM cache memories suffer from single event upset (SEU) faults induced by energetic particles such as neutron and alpha particles. To protect these caches, designers often use error detection and correction codes, which typically provide single-bit error detection and even correction. However, these codes have low error detection capability or incur significant performance penalties. In this paper, a protected cache scheme based on the variable associativity of sets is presented. In this scheme, cache space is divided into sets of different sizes with variable tag field lengths. The other remained bits of tags are used for protecting the tag using a new protection code. This leads to protect the cache without compromising performance and area with respect to the similar one, fully associative cache. The scheme provides high SEU detection coverage as well as high performance. Moreover, reliability and mean-time-to-failure (MTTF) equations are derived and estimated. The results obtained from fault injection experiments and several trace files from SPEC2000 reveal that the proposed scheme exhibits a good performance near to fully associative cache but can detect high percent of SEU faults.     

On the Extendibility of Near-MDS Elliptic Codes

The Main Conjecture on maximum distance separable (MDS) codes states that, except for some special cases, the maximum length of a q-ary linear MDS code of is q+1. This conjecture does not hold true for near maximum distance separable codes because of the existence of q-ary near-MDS elliptic codes having length bigger than q+1. An interesting related question is whether a near-MDS elliptic code may be extended to a longer near-MDS code. In this paper we prove some non-extendibility results for certain near-MDS elliptic codes.     

On minimum distance bounds for abelian codes

This paper is an exposition of two methods of formulating a lower bound for the minimum distance of a code which is an ideal in an abelian group ring. The first, a generalization of the cyclic BCH (Bose-Chaudhuri-Hoquenghem) bound, was proposed by Camion [2]. The second method, presented by Jensen [4], allows the application of the BCH bound or any of its improvements by viewing an abelian code as a direct sum of concatenations of cyclic codes. This second method avoids the mathematical analysis required for a direct generalization of a cyclic bound to the abelian case. It can produce a lower bound that improves the generalized BCH bound. We present simple algorithms for 1) deriving the generalized BCH bound for an abelian code 2) determining direct sum decompositions of an abelian code to concatenated codes and 3) deriving a bound on an abelian code, viewed as a direct sum of concatenated codes, by applying the cyclic BCH bound to the inner and outer code of each concatenation. Finally, we point out the applicability of these methods to codes that are not ideals in abelian group rings.