We present novel techniques to verify the linearity of$\mathbb{Z}_{2^{L}}-\mathbf{linear}$codes, i.e., the binary codes obtained as the image of the generalized Gray map of$\mathbb{Z}_{2^{L}}-\mathbf{additive}$codes. The central idea is the definition of two auxiliary binary codes, which we denote by associated and decomposition codes. Since$\mathbb{Z}_{2^{L}}-\mathbf{linear}$codes can be linear or nonlinear, as a consequence of our contributions, we are able to construct families of linear$\mathbb{Z}_{2^{L}}-\mathbf{linear}$codes from nested Reed-Muller and cyclic codes. This work expands on previous results from the literature, where the linearity of$\mathbb{Z}_{2^{L}}. \mathbf{linear}$codes was established with respect to the kernel of the underlying$\mathbb{Z}_{2^{L}}-\mathbf{additive}$code and/or operations on$\mathbb{Z}_{2^{L}}$.

Recently, a design criterion depending on a lattice’s volume and theta series, called the secrecy gain, was proposed to quantify the secrecy-goodness of the applied lattice code for the Gaussian wiretap channel. To address the secrecy gain of Construction A4 lattices from formally self-dual$ \mathbb {Z}_{4}$-linear codes, i.e., codes for which the symmetrized weight enumerator (swe) coincides with the swe of its dual, we present new constructions of$ \mathbb {Z}_{4}$-linear codes which are formally self-dual with respect to the swe. For even lengths, formally self-dual$ \mathbb {Z}_{4}$-linear codes are constructed from nested binary codes and double circulant matrices. For odd lengths, a novel construction called odd extension from double circulant codes is proposed. Moreover, the concepts of Type I/II formally self-dual codes/unimodular lattices are introduced. Next, we derive the theta series of the formally unimodular lattices obtained by Construction A4 from formally self-dual$ \mathbb {Z}_{4}$-linear codes and describe a universal approach to determine their secrecy gains. The secrecy gain of Construction A4 formally unimodular lattices obtained from formally self-dual$ \mathbb {Z}_{4}$-linear codes is investigated, both for even and odd dimensions. Numerical evidence shows that for some parameters, Construction A4 lattices can achieve a higher secrecy gain than the best-known formally unimodular lattices from the literature. Results concerning the flatness factor, another security criterion widely considered in the Gaussian wiretap channel, are also discussed.

In contrast to binary codes, odd-length self-dual codes exist over the integers modulo 4. Lately, the use of lattices constructed from codes over ℤ4to guarantee secure communication in a Gaussian wiretap channel was proposed and shown to exceed the performance of lattices from binary codes. This performance is measured regarding the secrecy gain, a criterion that depends on a lattice’s volume and theta series. Formally unimodular lattices, i.e., lattices with the same theta series as their dual, have presented promising results with respect to the secrecy gain. While previous contributions in the literature were mainly focused on even-dimensional lattices, this paper addresses the secrecy gain of odd-dimensional formally unimodular lattices obtained from codes over ℤ4, together with a novel construction of such codes.

This paper introduces the family of lattice-like packings, which generalizes lattices, consisting of packings possessing periodicity and geometric uniformity. The subfamily of formally unimodular (lattice-like) packings is further investigated. It can be seen as a generalization of the unimodular and isodual lattices, and the Construction A formally unimodular packings obtained from formally self-dual codes are presented. Recently, lattice coding for the Gaussian wiretap channel has been considered. A measure called the secrecy function was proposed to characterize the eavesdropper’s probability of correctly decoding. The aim is to determine the global maximum value of the secrecy function, called (strong) secrecy gain. We further apply lattice-like packings to coset coding for the Gaussian wiretap channel and show that the family of formally unimodular packings shares the same secrecy function behavior as unimodular and isodual lattices. We propose a universal approach to determine the secrecy gain of a Construction A formally unimodular packing obtained from a formally self-dual code. From the weight distribution of a code, we provide a necessary condition for a formally self-dual code such that its Construction A formally unimodular packing is secrecy-optimal. Finally, we demonstrate that formally unimodular packings/lattices can achieve higher secrecy gain than the best-known unimodular lattices.

A simple trellis based algorithm to compute the equivocation of a transmitted codeword, conditioned on the channel output, is presented.

Lattice coding for the Gaussian wiretap channel is considered, where the goal is to ensure reliable communication between two authorized parties while preventing an eavesdropper from learning the transmitted messages. Recently, a measure called secrecy gain was proposed as a design criterion to quantify the secrecy-goodness of the applied lattice code. In this paper, the theta series of the so-called formally unimodular lattices obtained by Construction A4from codes over ${{\mathbb{Z}}_4}$ is derived, and we provide a universal approach to determine their secrecy gains. Initial results indicate that Construction A4lattices can achieve a higher secrecy gain than the best-known formally unimodular lattices from the literature. Furthermore, a new code construction of formally self-dual ${{\mathbb{Z}}_4}$-linear codes is presented.

Motivated by applications in reliable and secure communication, we address the problem of tiling (or partitioning) a finite constellation in$\mathbb{Z}_{2^{L}}^{n}$by subsets, in the case that the constellation does not possess an abelian group structure. The property that we do require is that the constellation is generated by a linear code through an injective mapping. The intrinsic relation between the code and the constellation provides a sufficient condition for a tiling to exist. We also present a necessary condition. Inspired by a result in group theory, we discuss results on tiling for the particular case when the finer constellation is an abelian group as well.

The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average weight spectrum is presented. For LDPC codes from the Gallager ensemble and the Richardson-Urbanke ensemble, new upper bounds on the ML decoding performance based on computing the rank of submatrices of the code parity-check matrix are derived. A new lower bound on the ML decoding threshold followed from the latter error probability bound is obtained. An improved lower bound on the error probability for codes with a known estimate on the minimum distance is presented as well. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the simulated belief propagation and ML decoding performance and simulated performance of the best known improved iterative decoding techniques, as well as, with the derived upper bounds on the ML decoding performance and with decoding thresholds obtained by the density evolution technique.

A systematic convolutional encoder of rate (n-1)/n and maximum memory D generates a code of free distance at most V = D + 2 and, at best, a column distance profile (CDP) of [2,3, .. . , D]. A code is memory maximum distance separable if it possesses this CDP. Applied on a communication channel over which packets are transmitted sequentially and which loses (erases) packets randomly, such a code allows the recovery from any pattern of j erasures in the first j n-packet blocks for jm- 1)/pmand V equal to 3 over GF(pm) and rate (2m-1-1)/2m-1and V equal to 4 over GF(2m) are presented, which provide optimum values of V in their respective cases. A search algorithm is also developed, which produces new codes for V for field sizes 2m≤ 214. Using a complete search version of the algorithm, the maximum value of V, and codes that achieve it, are determined for all code rates ≥ 1/2 and every field size GF(2m) for m ≤ 5 (and for some rates for m = 6).

This paper discusses a new channel model and code design for the reader-to-tag channel in near-field passive radio frequency identification (RFID) systems using inductive coupling as a power transfer mechanism. If the receiver resynchronizes its internal clock each time a bit is detected, the bit-shift channel used previously in the literature to model the reader-to-tag channel needs to be modified. In particular, we propose a discretized Gaussian shift channel as a new channel model in this scenario. We introduce the concept of quantifiable error avoidance, which is much simpler than error correction. The capacity is computed numerically, and we also design some new simple codes for error avoidance on this channel model based on insights gained from the capacity calculations. Finally, some simulation results are presented to compare the proposed codes to the Manchester code and two previously proposed codes for the bit-shift channel model.

In this work, we consider the power spectrum of error-control codes designed for the reader-to-tag channel in near-field passive radio frequency identification (RFID) systems using inductive coupling as a power transfer mechanism. In contrast to previous works, binary phase-shift keying is considered, and the power spectral density is computed for two of the codes (and one runlength constraint) considered in a recent paper by Barbero et al. (Inf. Theory Appl., San Diego, CA, 2011), and for two new codes introduced in this paper. Furthermore, we compute the total power transferred to the tag as a function of the inter-coil separation for different codes (and one runlength constraint).

Inductive coupling is a technique wherein one device (the reader) induces an electrical current in another device (the tag), thereby providing not only power for the tag, but also a communication channel. In this paper, we focus exclusively on the reader-to-tag channel. The first part of this paper presents modulation codes that possess a high minimum and a high average power. This is important, since the tag gets its entire power from the received signal, and the information should be modulated in a way that maximizes the power transferred to the tag. The presented modulation codes compare favorably to codes used in radio frequency identification applications today. The second part of the paper describes modulation codes with some error-correcting capabilities. In fact, most errors in the reader-to-tag channel are due to incorrect timing. Here, we propose to model the timing errors in the reader-to-tag communication channel by a simple bit-shift channel, and we will present optimal (in the sense of maximizing the code rate for a given block length) single bit-shift error-correcting codes for this simple bit-shift channel that also have large average power.

In an earlier transactions paper, Rosnes and Ytrehus presented an efficient algorithm for determining all stopping sets of low-density parity-check (LDPC) codes, up to a specified weight, and also gave results for a number of well-known codes including the family of IEEE 802.16e LDPC codes, commonly referred to as the WiMax codes. It is the purpose of this short paper to review the algorithm for determining the initial part of the stopping set weight spectrum (which includes the codeword weight spectrum), and to provide some improvements to the algorithm. As a consequence, complete stopping set weight spectra up to weight 32 (for selected IEEE 802.16e LDPC codes) can be provided, while in previous work only stopping set weights up to 28 are reported. In the published standard for the IEEE 802.16e codes there are two methods of construction presented, depending upon the code rate and the code length. We compare the stopping sets of the resulting codes and provide complete stopping set weight spectra (up to five terms) for all IEEE 802.16e LDPC codes using both construction methods.

In this work, we will consider coding for a bit-shift channel with applications to inductively coupled channels. Inductive coupling is a technique wherein one device (the reader) induces an electrical current in another device (the tag), thereby providing not only power for the tag, but also a communications channel. Most errors in the reader-to-tag channel are due to incorrect timing. In this work, we propose to model the timing errors in the reader-to-tag communications channel by a simple bit-shift channel. We will present optimal single bit-shift error-correcting codes for this simple bit-shift channel that also have large average power. This is important, since the tag gets its entire power from the received signal, and the information should be modulated in a way that maximizes the power transferred to the tag.

Consider a lossy communication channel for unicast with zero-delay feedback. For this communication scenario, a simple retransmission scheme is optimum with respect to delay. An alternative approach is to use random linear coding in automatic repeat-request (ARQ) mode. We extend the work of Shrader and Ephremides in [1], by deriving an expression for the delay of random linear coding over a field of infinite size. Simulation results for various field sizes are also provided.

In this work, we introduce an efficient algorithm to find all stopping sets, of size less than some threshold, of a fixed low-density parity-check (LDPC) matrix. The solution is inspired by the algorithm proposed by Rosnes and Ytrehus in 2005 to find an exhaustive list of all small-size turbo stopping sets in a turbo code. The efficiency of the proposed algorithm is demonstrated by several numerical examples. For instance, we have applied the algorithm to the well-known (3, 5)-regular (155, 64) Tanner code and found all stopping sets of size at most 18 in about 1 min on a standard desktop computer. Also, we have verified that the minimum stopping set size of the (4896, 2474) Ramanujan-Margulis code is indeed 24, and that the corresponding multiplicity is exactly 204. Furthermore, we have applied the algorithm to the IEEE 802.16e LDPC codes and determined the minimum stopping set size and the corresponding multiplicity exactly for these codes. Finally, as an application, we present a greedy algorithm to find a small number of redundant parity checks to add to the original parity-check matrix in order to remove all stopping sets in the corresponding Tanner graph of size less than the minimum distance. An extensive case study of the (155, 64) Tanner code illustrates the usefulness of the algorithm, and we present a 110 times 155 redundant parity-check matrix for this code with no stopping sets of size less than the minimum distance. Simulation results of iterative decoding on the binary erasure channel show performance improvements for low-to-medium erasure probabilities when this redundant parity-check matrix is used for decoding.

The linear information flow (LIF) algorithm and its relatives are the most efficient centralized algorithms known for finding network encoding equations for multicast communication. This paper examines the performance of the LIFE (linear information flow on edges) algorithm on a "real" network, through the use of a simulation model. We present results on the algorithm's ability to encode in a finite field of given cardinality, and on the efficiency of the randomized version of the algorithm.

In this work, we introduce an efficient algorithm to find all stopping sets of size less than some threshold of a fixed low-density parity-check (LDPC) matrix. The solution is inspired by the algorithm proposed by Rosnes and Ytrehus in 2005 to find an exhaustive list of all small-size turbo stopping sets in a turbo code. The efficiency of the proposed algorithm is demonstrated by several numerical examples. For instance, we have applied the algorithm to the well-known (3, 5)-regular (155,64) Tanner code and found all stopping sets of size at most 18 in about one minute on a standard desktop computer. Also, we have verified that the minimum stopping set size of the (4896,2474) Ramanujan-Margulis code is indeed 24, and that the corresponding multiplicity is exactly 204.

This paper is devoted to the finite-length analysis of turbo decoding over the binary erasure channel (BEC). The performance of iterative belief-propagation decoding of low-density parity-check (LDPC) codes over the BEC can be characterized in terms ofstopping sets. We describe turbo decoding on the BEC which is simpler than turbo decoding on other channels. We then adapt the concept of stopping sets to turbo decoding and state an exact condition for decoding failure. Apply turbo decoding until the transmitted codeword has been recovered, or the decoder fails to progress further. Then the set of erased positions that will remain when the decoder stops is equal to the unique maximum-sizeturbo stopping setwhich is also a subset of the set of erased positions. Furthermore, we present some improvements of the basic turbo decoding algorithm on the BEC. The proposed improved turbo decoding algorithm has substantially better error performance as illustrated by the given simulation results. Finally, we give an expression for the turbo stopping set size enumerating function under the uniform interleaver assumption, and an efficient enumeration algorithm of small-size turbo stopping sets for a particular interleaver. The solution is based on the algorithm proposed by Garelloet al.in 2001 to compute an exhaustive list of all low-weight codewords in a turbo code.

The aim of this paper is to extend some basic concepts related to the Maximum Likelihood decoding of codes on the Z-channel, which is a particular, but very important, example of an asymmetric channel. We study distance properties of linear codes over the Z-channel, in order to define a suitable metric for the implementation of a Maximum Likelihood decoder on the channel. A combinatorial expression for an approximation on the probability of incorrect Maximum Likelihood decoding is also provided, and comparisons are given to evaluate the tightness of the estimation, when a Hamming code, a Turbo code and an LDPC code are used for communicating over the Z-channel.

In this paper, we introduce an algorithm to optimize the performance in the error-floor region of bit-interleaved turbo-coded modulation (BITCM) on the additive white Gaussian noise channel. The key ingredient is an exact turbo code weight distribution algorithm producing a list of all codewords in the underlying turbo code of weight less than a given threshold. In BITCM, the information sequence is turbo-encoded, bit-interleaved, and mapped to signal points in a signal constellation. Using the union-bounding technique, we show that a well-designed bit interleaver is crucial to have a low error floor. Furthermore, the error-rate performance in the waterfall region depends on the bit interleaver, since the level of protection from channel noise on the bit level depends on the bit position and the neighboring bit values within the same symbol in the transmitted sequence. We observe a tradeoff between error-rate performance in the waterfall and error-floor regions, as illustrated by an extensive case study of a high-rate BITCM scheme. This tradeoff is typical in iterative decoding of turbo-like codes. The reported case study shows that it is possible to design bit interleavers with our proposed algorithm with equal or better performance in the waterfall region and superior performance in the error-floor region, compared with randomly generated bit interleavers. In particular, we were able to design BITCM schemes with maximum-likelihood decoding frame-error rates of 10-12and 10-17at 2.6 and 3.8 dB away from unconstrained channel capacity, at spectral efficiencies of 3.10 and 6.20 b/s/Hz using square 16 and 256-quadrature amplitude modulation signal constellations, respectively

This correspondence addresses the problem of finding the network encoding equations for error-free networks with multiple sources and sinks. Previous algorithms could not cope with cyclic networks. Networks that are cyclic in three different senses are considered in this correspondence, and two extensions of the polynomial time Linear Information Flow (LIF) algorithm are presented. The first algorithm will produce the network encoding equations for a network which can be cyclic, unless the actual flow paths form cycles. The second algorithm will work also when the flow paths form simple cycles. Finally an example of a third kind of cyclic network, where the previous algorithms will fail, is given. However, a binary encoding is provided also in this case.

In this work we consider the design of good rate-compatible puncturing patterns for turbo codes in the error floor region. The key ingredient is an exact turbo code weight distribution algorithm producing a list L of all codewords in a turbo code of weight less than a given threshold. The proposed puncturing pattern design algorithm is a two step procedure. In the first step of the algorithm the bit-positions to be punctured are chosen sequentially in a greedy manner. In more detail, we choose at each iteration step the bit-position that is contained in the fewest number of minimum weight codewords from L. Since the list L is not necessarily exhaustive after puncturing (i.e., it does not necessarily contain all codewords of weight less than some threshold of the punctured code), the list is recomputed after a predetermined number of bit-position selections. The second part of the algorithm uses the chosen bit-positions as a starting point for local hill climbing. Note that the algorithm produces families a rate-compatible puncturing patterns for turbo codes. When only the first step of the algorithm is performed, larger families of rate-compatible puncturing patterns are constructed. We illustrate the usefulness of the proposed algorithm by some case studies on both short and moderate-length turbo codes. The reported case studies show that it is possible to improve the minimum distance to some extent with irregular puncturing compared to regular puncturing

This paper is devoted to the finite-length analysis of turbo decoding over the binary erasure channel (BEC). The performance of iterative belief-propagation (BP) decoding of low-density parity-check (LDPC) codes over the BEC can be characterized in terms of stopping sets. In the first part we describe turbo decoding on the BEC which is simpler than turbo decoding on other channels. We then adapt the concept of stopping sets to turbo decoding and state an exact condition for decoding failure. Apply turbo decoding until the transmitted codeword has been recovered, or until the decoder fails to progress further. Then the set of erased positions that will remain when the decoder stops is equal to the unique maximum size turbo stopping set which is also a subset of the set of erased positions. In the second part we present some improvements of the basic turbo decoding algorithm on the BEC. The proposed improved turbo decoding algorithm has substantially better error performance as illustrated by the given simulation results

The performance of turbo decoding on the binary erasure channel (BEC) can be characterized in terms of turbo stopping sets. Apply turbo decoding until the transmitted codeword has been recovered, or until the decoder fails to progress further. Then the set of erased positions that will remain when the decoder stops is equal to the unique maximum size turbo stopping set which is also a subset of the set of erased positions. The concept of turbo stopping sets is an adaptation of stopping sets from the theory of iterative belief-propagation (BP) decoding of low-density parity-check (LDPC) codes. The main results in this work are an expression for the turbo stopping set size enumerating function under the uniform interleaver assumption, and an efficient enumeration algorithm of small-size turbo stopping sets for a particular interleaver. The solution is based on the algorithm proposed by Garello et al. in 2001 to compute an exhaustive list of all low-weight codewords in a turbo code

We discuss algorithms for determining exactly the lower terms of the weight distribution of a turbo code. Several improvements on the recently introduced algorithm by Garello et al. are outlined. The techniques presented in this letter improve the observed asymptotic complexity by a factor proportional to the information length. As an example, the improved algorithm is applied to the determination of the minimum distance of all universal mobile telecommunications system turbo codes. We further apply the improved algorithm to high-rate turbo codes using high-rate nonpunctured constituent codes. To reduce complexity, the constituent codes are represented by a minimal information bit-oriented trellis.

In this paper we introduce an algorithm to optimize the performance in the error floor region of bit-interleaved turbo-coded modulation (BITCM) on the additive white Gaussian noise (AWGN) channel. The key ingredient is an exact turbo code weight distribution algorithm producing a list of all codewords in the underlying turbo code of weight less than a given threshold. In BITCM, the information sequence is turbo-encoded, bit- interleaved, and mapped to signal points in a signal constellation. Using the union bounding technique, we show that a well-designed bit-interleaver is crucial to have a low error floor. Furthermore, the error rate performance in the waterfall region depends on the bit-interleaver, since the level of protection from channel noise on the bit-level depends on the bit-position and the neighboring bit values within the same symbol in the transmitted sequence. We observe a trade-off between error rate performance in the waterfall and error floor regions as illustrated by an extensive case study of a high-rate BITCM scheme. The reported case study shows that it is possible to design bit-interleavers with our proposed algorithm with equal or better performance in the waterfall region and superior performance in the error floor region compared to randomly generated bit-interleavers. In particular, we were able to design BITCM schemes with maximum-likelihood decoding frame error rates of 10/sup -12/ and 10/sup -17/ at 2.6 dB and 3.8 dB away from unconstrained channel capacity at spectral efficiencies of 3.10 and 6.20 b/s/Hz using square 16 and 256-QAM signal constellations, respectively.

In this work we introduce an algorithm to optimize the performance in the error floor region of bit-interleaved turbo-coded modulation (BITCM) on the additive white Gaussian noise (AWGN) channel. The key ingredient is an exact turbo code weight distribution algorithm producing a list of all codewords in the underlying turbo code of weight less than a given threshold. Using the union bounding technique, we show that a well-designed bit-interleaver is crucial to have a low error floor. Furthermore, the error rate performance in the waterfall region depends on the bit-interleaver, since the level of protection from channel noise on the bit-level depends on the bit-position and the neighboring bit values within the same symbol in the transmitted sequence. We observe a trade-off between error rate performance in the waterfall and error floor regions as illustrated by an extensive case study of a high-rate BITCM scheme.

We introduce general sphere packing bounds for convolutional codes. These improve upon the Heller bound [J.L.Heller (1968)] for high rate convolutional codes. For example, based on the Heller bound, McEliece [2, p. 1114] suggested that for a rate (n-1)/n code of free distance 5 with /spl nu/ memory elements in its minimum encoder, asymptotically as /spl nu/ /spl rarr/ /spl infin/ it holds that n /spl les/ 2/sup (/spl nu/+1)/2/. a simple corollary of our bounds shows that in this case, n /spl lsim/2/sup /spl nu//2/, an improvement by a factor of /spl radic/2. The bound can be further strengthened.

We apply principles from digital image correction to enhance the correction of two-dimensionally correlated unidirectional errors on a two-dimensional grid system. A restoration technique presented in Neifield et al. (1996) based on Markov random fields, is used to find an estimate of the error pattern. This estimate then in turn provides a priori information for use in a soft decoder for the actual code (e.g. LDPC decoder).

We introduce general sphere-packing bounds for convolutional codes. These improve upon the Heller (1968) bound for high-rate convolutional codes. For example, based on the Heller bound, McEliece (1998) suggested that for a rate (n - 1)/n convolutional code of free distance 5 with /spl nu/ memory elements in its minimal encoder it holds that n /spl les/ 2/sup (/spl nu/+1)/2/. A simple corollary of our bounds shows that in this case, n < 2/sup /spl nu//2/, an improvement by a factor of /spl radic/2. The bound can be further strengthened. Note that the resulting bounds are also highly useful for codes of limited bit-oriented trellis complexity. Moreover, the results can be used in a constructive way in the sense that they can be used to facilitate efficient computer search for codes.

The existence of a ternary [28, 6, 16] code is considered. We show that without loss of generality, a generator matrix of such a code must satisfy certain conditions. A computer search over all matrices that satisfy these conditions reveals that a ternary [28, 6, 16] code does not exist.

We present a new construction of block codes for the (1-D)-PR (partial response) channel. The codewords in the code correspond to constant-sum subsets of a difference set. It is shown that at the output of a noiseless (1-D)-PR channel; the minimum squared Euclidean distance of such a code is at least six, compared to two for the uncoded system. This construction yields larger code rates than previously known codes with the same minimum distance for large code lengths. The construction technique also imposes upper bounds on the decoding complexity of the codes.

A communication or storage system may use a coset of a binary convolutional code for both symbol synchronization and error control. To facilitate symbol synchronization, the coset must have a short maximum zero-run length L/sub max/. General upper and lower bounds on L/sub max/ were given previously by Hole. In this correspondence we use these bounds to identify which convolutional codes have cosets with short L/sub max/. For such a code, we then show how to determine a coset with the least possible L/sub max/ among all cosets of the code. Exact expressions for the least possible L/sub max/ of convolutional code cosets are given, and examples of such cosets with large free distances are tabulated. Bounds on L/sub max/ for cosets of block codes are also provided. It is indicated how to tighten the bounds for block codes satisfying the one-way chain condition. We show that the cosets obtained from traditional high-rate block code constructions have larger L/sub max/ than cosets of convolutional codes with approximately the same rates. In some systems the convolutional code cosets must have short maximum one-run lengths as well as short maximum zero-run lengths to avoid loss of symbol synchronization. It is shown how to determine convolutional codes whose cosets with least possible maximum zero-run lengths also have least possible maximum one-run lengths.

Constructions of [162,8,80] and [159,8,78] codes are given. This solves the open problems of finding the minimum length of binary codes of dimension S and minimum distances 78 and 80, respectively.

We present a new soft-decision decoding method for high-rate convolutional codes. The decoding method is especially well-suited for PUM convolutional codes. The method exploits the linearity of the parallel transitions in the trellis associated with PUM codes. We provide bounds on the number of operations per decoded bit, and show that this number is dependent on the weight hierarchy of the linear block code associated with the parallel transitions. The complexity of the new decoding method for PUM codes is compared to the complexity of Viterbi decoding of comparable punctured convolutional codes. Examples from a special class of PUM codes show that the new decoding method compares favorably to Viterbi decoding of punctured codes.

The minimum support weight, d/sub r/(C), of a linear code C over GF(q) is the minimal size of the support of an r-dimensional subcode of C. A number of bounds on d/sub r/(C) are derived, generalizing the Plotkin bound and the Griesmer bound, as well as giving two new existential bounds. As the main result, it is shown that there exist codes of any given rate R whose ratio d/sub rd/sub 1/ is lower bounded by a number ranging from (q/sup r/-1)/(q/sup r/-q/sup r-1/) to r, depending on R.>

The trellis complexity s(C) of an [n, k, d]-code C is investigated, in the case where the weights of nonzero codewords in C are confined to {d, /spl middotspl middotspl middot/, 2d-1}/spl cup/{n}. It is shown that s(C)/spl ges/k-1. Furthermore, s(C)=k-1 if the code is self-complementary. If the nonzero weights are confined to {d, /spl middotspl middotspl middot/, 2d-3}, then s(C)=k.>

A coset of a convolutional code may be used to generate a zero-run length limited trellis code for a 1-D partial-response channel. The free squared Euclidean distance, d/sub free//sup 2/, at the channel output is lower bounded by the free Hamming distance of the convolutional code. The lower bound suggests the use of a convolutional code with maximal free Hamming distance, d/sub max/(R,N), for given rate R and number of decoder states N. In this paper we present cosets of convolutional codes that generate trellis codes with d/sub free//sup 2/>d/sub max/(R,N) for rates 1/5/spl les/R/spl les/7/9 and (d/sub free//sup 2/=d/sub max/(R,N) for R=13/16,29/32,61/64, The tabulated convolutional codes with R/spl les/7/9 were not optimized for Hamming distance. Instead, a computer search was used to determine cosets of convolutional codes that exploit the memory of the 1-D channel to increase d/sub free//sup 2/ at the channel output. The search was limited by only considering cosets with certain structural properties. The R/spl ges/13/16 codes were obtained using a new construction technique for convolutional codes with free Hamming distance 4. Newly developed bounds on the maximum zero-run lengths of cosets were used to ensure a short maximum run length at the 1-D channel output.>

The generalized Hamming weight, d/sub r/(C), of a binary linear code C is the size of the smallest support of any r-dimensional subcode of C. The parameter d/sub r/(C) determines the code's performance on the wire-tap channel of Type II. Bounds on d/sub r/(C), and in some cases exact expressions, are derived. In particular, a generalized Griesmer bound for d/sub r/(C) is presented and examples are given of codes meeting this bound with equality.>

A binary, linear block code C with block length n and dimension n is commonly denoted by (n,k) or, if its minimum distance is d, by (n,k,d). The code's covering radius r(C) can be defined as the smallest number r such that any binary column vector of length (n-k) can be written as a sum of r or fewer columns of a parity-check matrix of C. An (n,k) code with covering radius r is denoted by (n,k)r. R.A. Brualdi et al., (1989) showed that l(m,r) is defined to be the smallest n such that an (n,n-m)r code exists. l(m,2) is known for m<or=6, while it is shown by Brualdi et al. that 17

Upper bounds are derived on the number of codewords in error-correcting (d,k)-constrained block codes. The author focuses on simple error-correcting schemes, such as single-error correction, since the recording channels on which these codes are used usually have a very low bit error rate. Multierror-correcting codes with a relatively short block length are not practical, since a high code rate is a major concern. The notation of a (d,k)-constrained block code is discussed. The concept of combined codes is introduced, several bounds are derived, and several examples are given.>

The mixed-error channel (MC) combines the binary symmetric channel and the peak shift channel. The construction of (d, k) constrained t-MC-error-correcting block codes is described. It is demonstrated that these codes can achieve a code rate close to the (d, k) capacity. The encoding and decoding procedures are described. The performance of the construction depends on a particular partitioning of (d, k) constrained block codes. This partitioning is discussed and various tables of codes are included. Examples on encoding/decoding and on code performance are given.>

The existence of a binary (25,8,10) code is considered. It is shown that such a code must have a generator matrix of a specific form. However, all generator matrices of this form were tested and none generated a (25,8,10) code. Thus, such a code does not exist.>

Letn(k,d)be the smallest integernsuch that a binary linear code of lengthn, dimensionk, and minimum distance at leastdexists. New results are given that improve the best previously known bounds onn(8,d).