The Plotkin construction combines two codes to a code of doubled length. It can be applied recursively. The class of Reed-Muller (RM) codes is a particular example. Exploiting a property of the code words constructed by the recursive Plotkin construction, we present novel soft-decision decoders. These are based on the decoding of hidden code words which are inherent contained in the constructed code words and can be uncovered by adding particular parts of the overall code word. The main idea is to use more than one decoding variant where each variant starts with the decoding of a different hidden code word. Given the decision of this first hidden code word allows error cancellation for the remaining decoding. The final decoding decision selects the best of the decisions of the used variants. The more variants are used the closer the performance gets to the maximum-likelihood (ML) decoding performance. This is verified by an ML-bound for the cases where the ML performance is not known. The decoding algorithms use only additions, comparisons, and sign operations. Further, due to the recursive structure, only relatively short codes have to be decoded, thus, the decoding complexity is very low. We also present a new decoder for first-order RM codes with low complexity. In addition, we introduce two novel classes of half-rate codes based on recursive Plotkin constructions with RM codes. We show that the novel soft decision decoders can also be applied to recursive Plotkin constructions with BCH codes and to particular classes of generalized concatenated codes (GCC).

This paper proposes a novel shift-sum decoding method for non-binary cyclic codes, which only requires finite field operations but yields advanced decoding performance. Using the cyclically different minimum-weight dual codewords (MWDCs) and their proper shifts, a frequency matrix can be obtained as a reliability metric for identifying the error positions and magnitudes. By analyzing the statistical distributions of the matrix entries, the rationale for the shift-sum decoding’s advanced error-correction capability is revealed. Based on this decoding method, a hard-decision iterative shift-sum (HISS) decoding algorithm is first proposed. It can correct errors beyond half of the code’s minimum Hamming distance. By further utilizing the reliability information obtained from the channel, a soft-decision iterative shift-sum (SISS) decoding algorithm is then proposed to improve the decoding performance. Both the HISS and the SISS algorithms are realized only with polynomial multiplications and numerical comparisons, which are hardware-friendly. To further improve the error-correction performance, the HISS and SISS algorithms can be integrated in a Chase decoding mechanism for handling the test-vectors. Simulation results on Reed-Solomon (RS) and non-binary BCH (NB-BCH) codes show that the proposed algorithms yield a competent decoding and complexity performances in comparison with the existing decoding algorithms.

Information set decoding is a method for soft-decision decoding of general linear binary codes. Its performance can be improved by reprocessing multiple bases. Different methods for choosing the bases are known. We present a novel method for basis selection using probability analysis. The sequence of bases is determined which maximizes the decoding performance. We present a method for approximating this sequence by updating the error probabilities of the received symbols and give an efficient implementation. Furthermore, we show that the concept of updating bit error probabilities can be extended from information set decoding to box and match decoding. Simulation results confirm the efficiency of the proposed decoders compared with regular information set decoding and other multibasis algorithms.

Reed-Muller (RM) codes have recently regained some interest in the context of low latency communications and due to their relation to polar codes. RM codes can be constructed based on the Plotkin construction. In this work, we consider concatenated codes based on the Plotkin construction, where extended Bose-Chaudhuri-Hocquenghem (BCH) codes are used as component codes. This leads to improved code parameters compared to RM codes. Moreover, this construction is more flexible concerning the attainable code rates. Additionally, new soft-input decoding algorithms are proposed that exploit the recursive structure of the concatenation and the cyclic structure of the component codes. First, we consider the decoding of the cyclic component codes and propose a low complexity hybrid ordered statistics decoding algorithm. Next, this algorithm is applied to list decoding of the Plotkin construction. The proposed list decoding approach achieves near-maximum-likelihood performance for codes with medium lengths. The performance is comparable to state-of-the-art decoders, whereas the complexity is reduced.

The binary primitive BCH codes are cyclic and are constructed by choosing a subset of the cyclotomic cosets. Which subset is chosen determines the dimension, the minimum distance and the weight distribution of the BCH code. We construct possible BCH codes and determine their coderate, true minimum distance and the non-equivalent codes. A particular choice of cyclotomic cosets gives BCH codes which are, extended by one bit, equivalent to Reed-Muller codes, which is a known result from the sixties. We show that BCH codes have possibly better parameters than Reed-Muller codes, which are related in recent publications to polar codes. We study the decoding performance of these different BCH codes using information set decoding based on minimal weight codewords of the dual code. We show that information set decoding is possible even in case of a channel without reliability information since the decoding algorithm inherently calculates reliability information. Different BCH codes of the same rate are compared and different decoding performances and complexity are observed. Some examples of hard decision decoding of BCH codes have the same decoding performance as maximum likelihood decoding. All presented decoding methods can possibly be extended to include reliability information of a Gaussian channel for soft decision decoding. We show simulation results for soft decision list information set decoding and compare the performance to other methods.

This paper proposes the low-complexity Chase (LCC) decoding using basis reduction (BR) interpolation for Reed-Solomon (RS) codes, namely the LCC-BR algorithm. With received soft information, a number of decoding test-vectors are formulated. The LCC-BR algorithm first constructs a common basis which will be utilized by the following individual basis constructions of all test-vectors. This eliminates the redundant computation in BR interpolation, resulting in a low decoding complexity. Moreover, the LCC-BR algorithm can decode each test-vector in parallel, lowering the decoding latency. This paper further proposes the progressive LCC-BR (PLCC-BR) algorithm that decodes the test-vectors sequentially and terminates once the intended message is found. This progressive decoding is realized without additional memory cost. Simulation results show the complexity and latency advantages of the proposed algorithms over the other benchmark algorithms.

This paper proposes a novel shift-sum decoding scheme for non-binary cyclic codes. Using minimum-weight dual codewords and their cyclic shifts, a reliability measure can be yielded as an indicator for the error position and the error magnitude. Based on this shift-sum decoding concept, a harddecision iterative decoding algorithm is proposed, which can correct errors beyond half of the code’s minimum Hamming distance. By utilizing reliability information from the channel, a soft-decision iterative decoding algorithm is further introduced to improve the decoding performance. These two shift-sum based iterative decoding algorithms are realized with polynomial multiplication and integer (or real number) comparisons, which are hardware-friendly. Simulation results on Reed-Solomon codes and non-binary BCH codes show the decoding potential of the proposed algorithms.

The interpolation based algebraic soft decoding yields a high decoding performance for Reed-Solomon (RS) codes with a polynomial-time complexity. Its computationally expensive interpolation can be facilitated using the module structure. The desired Gröbner basis can be achieved by reducing the basis of a module. This paper proposes the low-complexity Chase (LCC) decoding algorithm using this module basis reduction (BR) interpolation technique, namely the LCC-BR algorithm. By identifying η unreliable symbols, 2ηdecoding test-vectors will be formulated. The LCC-BR algorithm first constructs a common basis which will be shared by the decoding of all test-vectors. This eliminates the redundant computation in decoding each test-vector, resulting in a lower decoding complexity and latency. This paper further proposes the progressive LCC-BR algorithm that decodes the test-vectors sequentially and terminates once the maximum-likelihood decision decoding outcome is reached. Exploiting the difference between the adjacent test-vectors, this progressive decoding is realized without any additional memory cost. Complexity analysis shows that the LCC-BR algorithm yields a lower complexity and latency, especially for high rate codes, which will be validated by the numerical results.

The Koetter-Vardy (KV) algorithm achieves advanced decoding performance for Reed-Solomon (RS) codes but with a high computational cost. This paper studies the lowcomplexity KV decoding that utilizes the module minimization (MM) interpolation technique, namely the KV-MM algorithm. A module contains bivariate polynomials that interpolate all the prescribed points with their multiplicity. Presenting the module basis as a matrix over univariate polynomials, row operation further reduces it into the Gröbner basis, delivering the interpolated polynomial. We will also introduce the re-encoding transformed KV-MM algorithm by giving an explicit construction for the module basis. This research shows MM interpolation yields a remarkably lower complexity for KV decoding than the conventional Koetter's interpolation, especially for high rate codes. This is also true when the re-encoding transform is applied. This finding is a rectification of some earlier results.

We study Reed-Solomon codes over arbitrary fields, inspired by several recent papers dealing with Gabidulin codes over fields of characteristic zero. Over the field of rational numbers, we derive bounds on the coefficient growth during encoding and the bit complexity of decoding, which is polynomial in the code length and in the bit width of error and codeword values. The results can be generalized to arbitrary number fields.

The interpolation based algebraic decoding for Reed-Solomon (RS) codes can correct errors beyond half of the code's minimum Hamming distance through constructing a minimum polynomial Q(x,y) and finding its y-roots. The progressive algebraic soft decoding (PASD) constructs Q(x, y) with a progressively enlarged y-degree and terminates once the message is decoded, adapting the decoding capability and computation to the channel. This paper proposes the re-encoding transformed PASD algorithm, in which Q(x, y) is progressively constructed by the low-complexity module minimization (MM) technique. Re-encoding transform (ReT) results in a common divisor for polynomials of the image of the submodule basis. It can be removed, leading to a simpler image expansion and reduction. Consequently, Q(x,y) is constructed through the isomorphic image of the progressively enlarged submodule basis. Our complexity analysis characterizes the complexity reduction brought by the transform and shows high rate codes benefit a greater complexity reduction.

The interpolation‐based algebraic decoding for Reed–Solomon (RS) codes can correct errors beyond half of the code's minimum Hamming distance. Using soft information, the algebraic soft decoding (ASD) further improves the decoding performance. This paper presents a unified study of two classical ASD algorithms, the algebraic Chase decoding and the Koetter‐Vardy decoding. Their computationally expensive interpolation is solved by the module minimisation (MM) technique which consists of basis construction and basis reduction. Compared with Koetter's interpolation, the MM interpolation yields a smaller computational cost for the two ASD algorithms. Re‐encoding transform is further applied to reduce the decoding complexity by reducing the degree of module generators. Based on assessing the degree of module seeds, a complexity reducing approach is introduced to further facilitate the two ASD algorithms. Computational cost of the two algorithms as well as their re‐encoding transformed variants will be analysed. Performance of the two ASD algorithms will be compared under decoding expenditure benchmark, providing more practical insights of their applications.

The algebraic soft-decision decoding (ASD) of Reed–Solomon (RS) codes yields a competent decoding performance with a polynomial-time complexity. But its complexity remains high due to the interpolation that generates the interpolation polynomial$Q(x,y)$. The progressive ASD (PASD) algorithm has been introduced to construct$Q(x,y)$with a progressively enlarged$y$-degree, adjusting its error-correction capability and computation to the received information. However, this progressive decoding is realized at the cost of memorizing the intermediate decoding information. To overcome this challenge, this paper proposes a new PASD algorithm which is evolved from the ASD using module minimization (MM) interpolation. Polynomial$Q(x,y)$can be constructed through the image of the progressively enlarged submodule basis without the need of memorizing the intermediate decoding information, eliminating the memory cost of progressive decoding. The MM interpolation also attributes to a remarkably lower complexity than the original PASD algorithm. Furthermore, a complexity reducing variant is proposed based on assessing the degree of Lagrange interpolation polynomials. We also analyze the complexity of the proposed decoding methods and reveal their channel dependent feature. Our simulation results show their low-complexity and advanced decoding performances.

We present a generalisation of Twisted Reed-Solomon codes containing a new large class of MDS codes. We prove that the code class contains a large subfamily that is closed under duality. Furthermore, we study the Schur squares of the new codes and show that their dimension is often large. Using these structural properties, we single out a subfamily of the new codes which could be considered for code-based cryptography: These codes resist some existing structural attacks for Reed-Solomon-like codes, i.e. methods for retrieving the code parameters from an obfuscated generator matrix.

The algebraic soft decoding (ASD) algorithm achieves advanced decoding performance for Reed-Solomon (RS) codes. However, its complexity remains high making it impractical. This is due to the interpolation. The progressive ASD (PASD) algorithm adjusts the decoding computation to the reliability of received information. Its interpolation generates the intended polynomial Q(x, y) with a progressively enlarged y- degree, and terminates once the message is decoded. But this progressive decoding is realized at the cost of memorizing the intermediate decoding information. This paper proposes a new PASD algorithm, in which the progressive interpolation is realized by the module minimization (MM) technique. Polynomial Q(x, y) can be found through the progressively enlarged images of submodule's basis without memorizing the intermediate decoding information. The MM interpolation also grants it a significantly lower complexity than the original PASD algorithm that uses Koetter's interpolation. Our simulation results will verify its advanced decoding performance and low-complexity feature.

We define multi-block interleaved codes as codes that allow reading information from either a small sub-block or from a larger full block. The former offers faster access, while the latter provides better reliability. We specify the correction capability of the sub-block code through its gap t from optimal minimum distance, and look to have full-block minimum distance that grows with the parameter t. We construct two families of such codes when the number of sub-blocks is 3. The codes match the distance properties of known integrated-interleaving codes, but with the added feature of mapping the same number of information symbols to each sub-block. As such, they are the first codes that provide read access in multiple size granularities and correction capabilities.

This paper considers capacity and delay constraints for coded tunnels across an erasure channel which occurs on shared Internet satellite links. Such links are long latency bottlenecks with a limited memory input queue which drops packets when it overflows. The latency delays ARQ ACK feedback to senders, making it difficult for them to tune their packet transmission rate. This can cause the input queue to oscillate between empty and overflow. Queue oscillation leaves the link underutilised during the empty phases and slows down large packet flows. Channel coding can in principle provide goodput improvement in this scenario by letting senders accelerate to higher packet rates before burst losses occur and by mitigating exponential backoff after losses. However, this is only possible if the codes preserve sufficient spare channel transmission rate for the improved goodput to expand into. We formulate rate and delay constraints that such block codes must meet. Using loss data obtained on a purpose-built simulator network, we show that such coding is feasible in a practical scenario and that partial unit memory (PUM) codes are particularly suitable for this task. In this context, we propose a part-systematic encoding for PUM codes, which performs slightly better than non-systematic encoding.

For streaming codes an erasure channel is assumed and the decoding delay is one of the main parameters to be considered. In this paper the erasure correcting capability of unit memory convolutional codes based on disjoint RS codes is analyzed. We take a sliding window decoder approach, where only the most current information is decoded before sliding the window one time-step further. We show that when we restrict the decoding delay to a small value, these codes still achieve an excellent erasure correction performance. This makes these codes useful for streaming applications where low latency is required.

Gabidulin codes, originally defined over finite fields, are an important class of rank metric codes with various applications. Recently, their definition was generalized to certain fields of characteristic zero and a Welch-Berlekamp like algorithm with complexity O(n3) was given. We propose a new application of Gabidulin codes over infinite fields: low-rank matrix recovery. Also, an alternative decoding approach is presented based on a Gao type key equation, reducing the complexity to at least O(n2). This method immediately connects the decoding problem to well-studied problems, which have been investigated in terms of coefficient growth and numerical stability.

Information processing in biologically motivated Boolean networks is of interest in recent information theoretic research. One measure to quantify this ability is the well-known mutual information. Using Fourier analysis, we show that canalizing functions maximize mutual information between a single input variable and the outcome of a function with fixed expectation. A similar result can be obtained for the mutual information between a set of input variables and the output. Further, if the expectation of the function is not fixed, we obtain that the mutual information is maximized by a function only dependent on this single variable, i.e., the dictatorship function. We prove our findings for Boolean functions with uniformly distributed as well as product distributed input variables.

We investigate the mutual information of Boolean functions with noisy inputs. Therefore, we derive a relation between the noise sensitivity and the mutual information. Further, we apply Fourier analysis to give upper bounds on the noise sensitivity and lower bounds on the mutual information for canalizing and nested canalizing functions. From these bounds we conjecture the optimality of these classes of functions.

In this paper we present an algorithm based on the sum-product algorithm that finds elements in the preimage of a feed-forward Boolean networks given an output of the network. Our probabilistic method runs in linear time with respect to the number of nodes in the network. We evaluate our algorithm for randomly constructed Boolean networks and a regulatory network of Escherichia coli and found that it gives a valid solution in most cases.

Known properties of cyclic codes are used to give a unified description of many classical decoding algorithms for Reed-Solomon codes up to half the minimum distance. This description allows also simplified proofs for these decoders. Further, a novel decoding algorithm is derived using these properties directly and variants of a new error/erasure decoding algorithm are given. For decoding beyond half the minimum distance, a basis of all solutions for decoding is derived. This basis allows to use side information in order to decode beyond half the minimum distance. Other methods where this basis can be used are power decoding, also known as virtual syndrome extension, where additional equations are generated by taking powers of the received symbols, and interleaved Reed-Solomon codes. The extended Euclidean algorithm, which calculates the greatest common divisor, plays an essential role in many presented methods.

In this paper we investigate the properties of the generator matrices of a new class of convolutional codes, called product convolutional codes, which were previously defined and investigated by the authors. The new codes are constructed using the well-known method of the direct product for combining block codes. Convolutional codes are considered as block codes over the field of rational functions F(D). The description of convolutional codes as block codes allows the successful application of the direct product method to convolutional codes, and, in addition, leads to a general method to construct new convolutional codes based on already known combining methods for block codes. Expressions for the generator matrices of the product convolutional codes are given and several of their properties, which were not addressed before, are determined. The relationship between the properties of the direct product encoder generator matrix and the properties of the vertical and horizontal constituent encoders generator matrices is derived. Rational generator matrices, as well as polynomial generator matrices, are addressed.

Partial Unit Memory (PUM) codes are a special class of convolutional codes, which are often constructed by means of block codes. Decoding of PUM codes can take advantage of existing block decoders. The Dettmar - Sorger algorithm is an efficient decoding algorithm for PUM codes, but allows only low code rates. The same restriction holds for several known PUM code constructions. In this paper, an arbitrary-rate construction, the analysis of its distance parameters and a generalized decoding algorithm for these PUM codes of arbitrary rate are provided. The correctness of the algorithm is proven and it is shown that its complexity is cubic in the code length.

This paper presents a division algorithm to solve the key equation for Hermitian codes, which is capable of locating most error patterns with weight up to half the designed minimum distance. The algorithm has a structure similar to the Euclidean algorithm used in the decoding of Reed-Solomon codes, yet it is a little more complex because bivariate polynomials have to be used. We give simulation results for the decoding of several Hermitian codes of various rates over the finite field GF(24) to verify the claims.

Traditionally, multi-trial error/erasure decoding of Reed-Solomon (RS) codes is based on Bounded Minimum Distance (BMD) decoders with an erasure option. Such decoders have error/erasure tradeoff factor λ = 2, which means that an error is twice as expensive as an erasure in terms of the code's minimum distance. The Guruswami-Sudan (GS) list decoder can be considered as state of the art in algebraic decoding of RS codes. Besides an erasure option, it allows to adjust λ to values in the range 1BMDdecoding trials can result in lower residual codeword error probability than GS decoders with zGStrials, if zBMDis only slightly larger than zGS. This is of practical interest since BMD decoders generally have lower computational complexity than GS decoders.

(Partial) Unit Memory ((P)UM) codes provide a powerful possibility to construct convolutional codes based on block codes in order to achieve a high decoding performance. In this contribution, a construction based on Gabidulin codes is considered. This construction requires a modified rank metric, the so-called sum rank metric. For the sum rank metric, the free rank distance, the extended row rank distance and its slope are defined. Upper bounds for the free rank distance and the slope of (P)UM codes in the sum rank metric are derived. The construction of PUM codes based on Gabidulin codes achieves the upper bound for the free rank distance.

An efficient algorithm which synthesizes all shortest skew-feedback shift-registers (defined in the paper) generatingLsequences of varying length over a field is derived and its correctness is proved. It generalizes the Berlekamp-Massey algorithm and some other algorithms, and has time complexityO(LN2), whereNis the length of a longest sequence. The proposed algorithm can be applied for efficiently solving the key equation when decoding interleaved (or direct sum of) Gabidulin codes beyond half minimum distance. Those codes have many applications and, as shown by Kötter and Kschischang, can be used for random network coding.

An efficient algorithm synthesizing all shortestq-linearized-feedback shift-registers generating a given sequence of lengthNover a finite field \BBFqmis derived and its correctness is proved. This algorithm, which is a generalization of the Berlekamp-Massey algorithm, has time complexityO(lN)O(N2) operations in \BBFqm, wherelis the linearized complexity of the sequence. The algorithm can be applied for efficiently solving the key equation when decoding Gabidulin codes.

This paper presents a method to determine a set of basis polynomials from the extended Euclidean algorithm that allows Generalized Minimum Distance decoding of Reed-Solomon codes with a complexity of O(nd).

The problem of estimating the Fourier spectra of Boolean functions using noisy non-uniformly drawn random examples is considered. In particular, arbitrary product distributions on the n-dimensional attribute vectors are assumed. The attributes are disturbed by noise also following a product distribution. Under these conditions the problem of estimating the Fourier spectra is considered. A general expression is derived that allows the construction of estimators of the Fourier spectra. This results can be applied to learn functions that are concentrated on the lower part of their spectra. As an application of the presented results an algorithm is shown that infers the relevant variables of so-called 1-low Boolean juntas.

We investigate threshold-based multi-trial decoding of concatenated codes with an inner Maximum-Likelihood decoder and an outer error/erasure ℓ+1/ℓ-extended Bounded Distance decoder, i.e. a decoder which corrects ε errors and τ erasures if ℓ+1/ ℓε+τ≤ do-1, where dois the minimum distance of the outer code and ℓ ∈ ℕ\{0}. This is a generalization of Forney's GMD decoding, which was considered only for ℓ = 1, i.e. outer Bounded Minimum Distance decoding. One important example for ℓ+1/ℓ-extended Bounded Distance decoders is decoding of ℓ-Interleaved Reed-Solomon codes. Our main contribution is a threshold location formula, which allows to optimally erase unreliable inner decoding results, for a given number of decoding trials and parameter ℓ. Thereby, the term optimal means that the residual codeword error probability of the concatenated code is minimized. We give an estimation of this probability for any number of decoding trials.

An interleaved Gabidulin code is the direct sum of ℓ Gabidulin codes. We propose an efficient decoding algorithm that corrects with high probability errors of rank up to (ℓ/ℓ+1)(d-1), where d is the rank distance of the interleaved code. The probability of decoding failure is estimated. The proposed decoding is based on a multisequence linearized shift-register synthesis algorithm, given in the paper. The time complexity of the decoding algorithm is O(ℓd2).

In this paper we extend the algorithms for the termination and tailbiting of direct product convolutional codes, that we proposed in a previous paper, to the rate-k/n case. There, the relationship between the direct product encoder state sequence and the parameters of the vertical and horizontal constituent encoders was derived, and, given a generic information sequence, it was shown how to find the terminating sequence for the direct product encoder of Rate R = 1/n. An algorithm was also proposed for tailbiting rate-1/n direct product convolutional codes. In this paper, we investigate on the tailbiting failure conditions, which were not addressed before, and extend the proposed tailbiting algorithm to the general rate-k/n case.

We present and prove the correctness of an efficient algorithm that provides a basis for all solutions of a key equation in order to decode Gabidulin (G-) codes up to a given radius τ. This algorithm is based on a symbolic equivalent of the Euclidean Algorithm (EA) and can be applied for decoding of G-codes beyond half the minimum rank distance. If the key equation has a unique solution, our algorithm reduces to Gabidulin's decoding algorithm up to half the minimum distance. If the solution is not unique, we provide a basis for all solutions of the key equation. Our algorithm has time complexity O(τ2) and is a generalization of the modified EA by Bossert and Bezzateev for Reed-Solomon codes.

We investigate adaptive single-trial error/erasure decoding of binary codes whose decoder is able to correct ε errors and τ erasures if λε + ≤min-1. Thereby, dminis the minimum Hamming distance and λ ϵ R, 1 <; λ <; 2, is the tradeoff parameter between errors and erasures. The error/erasure decoder allows to exploit soft information by treating a set of most unreliable received symbols as erasures. The obvious question here is, how this erasing should be performed, i.e. how the unreliable symbols that must be erased in order to obtain the smallest possible residual codeword error probability can be determined. This was answered before for the case of fixed erasing, where only the channel state and not the individual symbol reliabilities of each received vector are taken into consideration. In this paper, we address the adaptive case, where the optimal erasing strategy is determined for every given received vector.

This paper presents a method to merge Generalized Minimum Distance decoding of Reed-Solomon codes with the extended Euclidean algorithm. By merge, we mean that the steps performed in Generalized Minimum Distance decoding are similar to those of the extended Euclidean algorithm. The resulting algorithm has a complexity of O(n2).

In this paper, a new approach for decoding low-rate Reed-Solomon codes beyond half the minimum distance is considered and analyzed. The maximum error correcting radius coincides with the error correcting radius of the Sudan algorithm published in 1997. However, unlike the Sudan Algorithm, the approach described here is not a list decoding algorithm, and is not based on polynomial interpolation. The algorithm in this paper is rather syndrome based, like classical algebraic decoding algorithms. The computational complexity of the new algorithm is of the same order as the complexity of the well-known Berlekamp-Massey algorithm. To decode errors beyond half the minimum distance, the new decoder is allowed to fail for some high-weight error patterns with a very small probability.

The subspace metric is a subject of intensive researche recently. Nevertheless not much is known about codes in this metric in general. In this paper, one class of subspace metric based codes is defined. This class is a generalization of a Koetter-Kshishang-Silva construction, namely, the lifting construction. Also, a quasi-Singleton bound is derived which is tighter than the Koetter-Kschischang bound for large dimensions of subspaces.

Consider a code C with Hamming distance d. Assume we have a decoder ¿ that corrects ¿ errors and ¿ erasures if ¿¿ + ¿ ¿ d - 1, where a real number 1qlof length nq, where l ¿ {1, 2, . . .} and ¿ = 1+1/l. We propose an m-trial generalized minimum distance (GMD) decoder based on ¿. Our approach extends results of Forney and Kovalev (obtained for ¿ = 2) to the whole given range of ¿. We consider both fixed erasing and adaptive erasing GMD strategies. For l > 1 the following approximations hold. For the fixed erasing strategy the error correcting radius is ¿F¿ d/2 (1 - l-m/2). For the adaptive erasing strategy, ¿A¿ d/2 (1 - l-2m) quickly approaches d/2 if l or m grows. The minimum number of decoding trials required to reach an error correcting radius d/2 is mA= 1/2 (logld + 1). This means that 2 or 3 trials are sufficient to reach ¿A= d/2 in many practical cases if l > 1.

In this letter, a low complexity decoding algorithm for binary linear block codes is applied to low-density paritycheck (LDPC) codes and improvements are described, namely an extension to soft-decision decoding and a loop detection mechanism. For soft decoding, only one real-valued addition per code symbol is needed, while the remaining operations are only binary as in the hard decision case. The decoding performance is considerably increased by the loop detection. Simulation results are used to compare the performance with other known decoding strategies for LDPC codes, with the result that the presented algorithms offer excellent performances at smaller complexity.

In this letter, an improved bit-flipping decoding algorithm for high-rate finite-geometry low-density parity-check (FG-LDPC) codes is proposed. Both improvement in performance and reduction in decoding delay are observed by flipping multiple bits in each iteration. Our studies show that the proposed algorithm achieves an appealing tradeoff between performance and complexity for FG-LDPC codes.

Interleaved Reed-Solomon codes are applied in numerous data processing, data transmission, and data storage systems. They are generated by interleaving several codewords of ordinary Reed-Solomon codes. Usually, these codewords are decoded independently by classical algebraic decoding methods. However, by collaborative algebraic decoding approaches, such interleaved schemes allow the correction of error patterns beyond half the minimum distance, provided that the errors in the received signal occur in bursts. In this work, collaborative decoding of interleaved Reed-Solomon codes by multisequence shift-register synthesis is considered and analyzed. Based on the framework of interleaved Reed-Solomon codes, concatenated code designs are investigated, which are obtained by interleaving several Reed-Solomon codes, and concatenating them with an inner code.

A novel method for joint decoding of interleaved Reed-Solomon (RS) codes is presented which is based on an extension of the Euclidean algorithm. This method differs from the known multi-sequence shift register algorithms which is shown by an example.

In [4] a metric for error correction in network coding is introduced. Also constant-dimension codes were introduced and investigated. Nevertheless little is known on codes in this metric in general. In this paper, several classes of codes are defined and investigated.

We consider Boolean functions with noisy inputs. I.e., each binary input is sent over a binary symmetric channel with crossover probability isin before fed into the function. By proving an upper bound for the average l-sensitivity, we show that Boolean functions with average sensitivity less or equal 1 will not amplify the noise at their input. This means, that on average the probability that the output of the function is different from the output of the same function without noise, is less or equal e.

Generalized Concatenated codes are a code construction consisting of a number of outer codes whose code symbols are protected by an inner code. As outer codes, we assume the most frequently used Reed-Solomon codes; as inner code, we assume some linear block code which can be decoded up to half its minimum distance. Decoding up to half the minimum distance of Generalized Concatenated codes is classically achieved by the Blokh-Zyablov-Dumer algorithm, which iteratively decodes by first using the inner decoder to get an estimate of the outer code words and then using an outer error/erasure decoder with a varying number of erasures determined by a set of pre- calculated thresholds. In this paper, a modified version of the Blokh-Zyablov-Dumer algorithm is proposed, which exploits the fact that a number of outer Reed-Solomon codes with average minimum distance d macr can be grouped into one single Interleaved Reed-Solomon code which can be decoded beyond d macr/2. This allows to skip a number of decoding iterations on the one hand and to reduce the complexity of each decoding iteration significantly - while maintaining the decoding performance - on the other.

Adaptive coding and modulation are well known techniques for enhancing the performance of systems transmitting over quasi-static fading channels. Especially their application in OFDM based systems promises gains in spectral efficiency. In former work we presented an efficient method for the joint optimization of code rate and modulation formats if rate-compatible punctured codewords are mapped onto sub-symbols with heterogeneous channel quality and modulation formats. In this paper, we demonstrate the application of our scheme to MIMO techniques. More specifically, we investigate non-orthogonal spatial multiplexing schemes in bit-interleaved coded OFDM systems. The techniques are evaluated within the context of the OFDMA/TDMA system designed within the EU FP6 Integrated Project WINNER.

This paper addresses space time convolutional code design using continuous phase modulation (CPM). The possibility of constructing full diversity space time codes is investigated. A linear modulation approximation to CPM is done. Using the Gram-Schmidt orthogonalization transform the CPM signal is generated as a vector with finite energy in a different Euclidean space. A serially concatenated CPM construction is considered in searching channel codes which are able to exploit maximum diversity. Design criteria based on the encoding scheme are derived for an arbitrary number of transmit antennas. The investigations are done for a quasi-static Rayleigh fading channel.

In this paper, a modified bit-flipping decoding algorithm for low-density parity-check (LDPC) codes is proposed. Both improvement in performance and reduction in decoding delay are observed by flipping multiple bits in each iteration. Our studies show that the proposed algorithm achieves an appealing tradeoff between performance and complexity for many constructions of LDPC codes.

Recently, active distance measures for trellis coded modulation (TCM) based on the Euclidean metric have been introduced which allow for a precise characterization of the TCM's error correcting capabilities in the additive white Gaussian noise channel. However, there exist concatenated coding schemes with TCM as constituent codes which apply puncturing to the TCM's code symbols and thus, the performance of these coding schemes is significantly determined by the Hamming distances of the constituent TCM. Hence, the family of active Hamming distance measures for TCM is introduced in this work, together with a matrix-based method to compute these distance measures. It is shown how they influence the performance of concatenated codes.

Achievable rate regions in broadcast channels are usually determined for infinite Gaussian input alphabets. Since these alphabets are not used for practical systems, we investigate the influence of finite signal constellations in the two user AWGN broadcast channel. We show that results derived with Gaussian inputs are not transferable to the finite case. For scenarios where the rate of one user should be maximized whilst a required rate for the other user is delivered we establish design rules.

Irregular low-density parity-check (LDPC) codes constructed from small protographs are one of the most powerful LDPC codes. In this paper, we show that the performance of LDPC codes based on small protographs can be further improved by using different transmission energies for every variable node of the protograph. Thus, a protograph is now described by a set of variable nodes, a set of check nodes, edges connecting variable nodes and check nodes, and the transmission energy used for every variable node, which is called the energy distribution. We optimize the energy distribution of protographs by choosing the energy distribution with the highest threshold calculated with a generalization of the discretized density evolution. Furthermore, we show by simulations that the performance of long LDPC codes based on protographs can be improved as expected from the thresholds.

Low-density parity-check (LDPC) codes are very powerful error correction codes for bit-interleaved coded modulation (BICM) schemes. In BICM schemes the bits of one symbol have unequal error protection. In this paper, we show how to improve the performance of given LDPC codes by mapping the variable nodes of certain degree in a special way to the different bit levels. Since the equivalent binary-input component channels for each individual bit level are not symmetric, we use the tool of i.i.d. channel adapters to force symmetry. After that, we optimize the mapping of the LDPC code to the different bit levels by a downhill algorithm that uses a generalized discretized density evolution to calculate the thresholds. We show by thresholds and by simulations that a special mapping of LDPC codes lowers the bit error rates compared to a random mapping of LDPC codes.

Reed-Solomon codes have become one of the most popular classes of error correcting codes, since they can be decoded very efficiently up to half their minimum distance using syndrome-based techniques. Modern interpolation-based decoding algorithms like the Sudan algorithm allow for decoding error patterns beyond half the minimum distance in polynomial time. Recently, a syndrome-based decoding algorithm has been proposed, which virtually extends a Reed-Solomon code into an Interleaved Reed-Solomon (IRS) code. This method is competitive to the classical Sudan algorithm. In this paper, a new method for decoding IRS codes is described, which combines the idea of syndrome extension and the idea of collaboratively decoding IRS codes to increase the decoding radius of low-rate IRS codes.

It is well known that convolutional codes can be considered as block codes over a field of rational functions. Being a block code, every convolutional code has "block" distance df. The free distance df of a convolutional code is lower bounded by d,B, dfges dB. With this approach, every method of designing or combining block codes immediately gives a method to design or to combine convolutional codes. The block distance dBof the new convolutional code is known (or can be estimated), this gives a lower bound for the free distance of the new convolutional code. We investigate the properties of block distance and show that block distance of blocked convolutional codes reaches free distance. The proposed method is demonstrated for Reed-Solomon codes, for the direct product codes and for bipartite graph codes. For these examples, bounds of type dfges dBand improved bounds are obtained.

We consider multidimensional bit interleaved coded modulation with iterative decoding (MD-BICM-ID) using 8-PSK constellations. We show that an optimum MD-labeling with a designed interleaver outperforms the two dimensional BICM-ID in the whole SNR region when modulation doping is used to compensate for the loss at the low SNR regions. In addition to this, a new interleaver design for MD-BICM-ID is introduced.

The influence of time-varying cyclic delay diversity (TV-CDD) on the channel fading correlation properties is analyzed in this paper. TV-CDD is an attractive transmit diversity technique which increases not only the frequency diversity like pure CDD but also the time diversity in orthogonal frequency division multiplexing (OFDM) based systems. These transmit diversity schemes are characterized by no need of additional complexity at the receiver to exploit the increased transmit diversity. This paper gives first investigations regarding the resulting channel characteristics from TV-CDD and the impact on the system performance. Due to the increased frequency and time selectivity and a larger channel delay, an unintended higher channel estimation effort is possible. Therefore, we analyze the choice of the maximum cyclic delay. We show that the resulting channel for TV-CDD can be seen as an uncorrelated Rayleigh channel (except for the first sub-carrier) for a large maximum cyclic delay. Furthermore, analysis and simulation results demonstrate a feasible choice of small time-varying cyclic delays for guaranteeing the standard conformability of the TV- CDD technique at the receiver without significant performance degradations.

We introduce hierarchical woven coded continuous phase frequency-shift keying (hierarchical WCCPFSK) as the serial concatenation of different outer convolutional codes and inner CPFSK. We compare it to WCCPFSK with identical outer convolutional codes. With the proposed code combinations, hierarchical WCCPFSK achieves superior decoding capability. Simulations show that it performs better at medium SNRs.

We calculate the rank of low-density parity-check (LDPC) matrices based on Vandermonde matrix like constructions. In the case of prime fields the rank is given exactly. We show that LDPC codes based on RS codes are a special case of the Vandermonde based construction, thus also for these LDPC matrix construction, the rank calculation is valid. However, for extension fields the calculation is more sophisticated because of the nilpotent property of the parity check matrix. Therefore we can give presently only a bound for the rank in case of binary extension fields

In this paper, we describe a method, how to optimize the asymptotic puncturing distributions for low-density parity-check codes constructed with different algorithms. Therefore, we generalize the discretized density evolution such that we can take care of the structure of the code. We show by density evolution and by simulations that even for the same degree distributions the optimized asymptotic puncturing distributions vary considerably for different construction algorithms. Furthermore, we demonstrate the performance gain by using the designed puncturing distributions compared to known puncturing distributions

It is known, that interleaved Reed-Solomon codes can be decoded algebraically beyond half the minimum distance using collaborative decoding strategies. Based on the same principles, we suggest a new effective algebraic decoding method, which is able to decode a single low rate Reed-Solomon code beyond half the minimum distance. This new algorithm is based on multi-sequence shift-register synthesis, and is able to correct errors within a correcting radius similar to the Sudan algorithm. In contrast to the Sudan algorithm, which may obtain a list of codewords, our algorithm yields a decoding failure if there does not exist a unique solution. However, the probability of such a failure is very small

We propose a multidimensional constellation labeling for bit interleaved space time coded modulation with iterative decoding (BI-STCM-ID) using the Alamouti scheme and one receive antenna. The labeling of two 16-QAM signals are designed jointly and optimized using the reactive tabu search (RTS) algorithm with a slight modification in the fitness function of the two dimensional labeling. The proposed multidimensional labeling provided 4 dB coding gain over the best known two dimensional labeling

In this paper, a low complexity algorithm for binary linear block codes is applied to low-density parity-check (LDPC) codes and improvements are described, namely an extension to soft-decision decoding and a loop detection mechanism. For soft decoding, only one real-valued addition per code symbol is needed, while the remaining operations are only binary as in the hard decision case. The decoding performance is considerably increased by the loop detection. Simulation results are used to compare the performance with other known decoding strategies for LDPC codes, with the result that the presented algorithms offer excellent performance at smaller complexity.

In this paper, an algorithm for low-density parity-check (LDPC) codes with reduced complexity is presented. The complexity reduction is achieved by calculating a linear function for updating the check nodes in each iteration, instead of an exponential and logarithmic function. The parameters of the linear function are optimized by density evolution. Simulation results show that there is nearly no loss in the performance by using this approximation compared to the exact calculation of the belief propagation decoding algorithm, even for very large block lengths.

We define and investigate the direct product of convolutional codes. Properties of generator and parity check matrices are considered. Free distance of a product convolutional code is estimated using both, active distances and the suggested concept of "block distances" of convolutional component codes. We show that every product convolutional code can be represented as a woven code

Decoding strategies based on ordered statistics have proven to be powerful in decoding binary linear block codes. However, for q-ary codes, the existing decoding methods are not suited very well, since the required reprocessing steps, which try all possible changes in several code symbols, cause a high computational complexity. This complexity can be reduced by using short lists of the most reliable symbols instead of trying all q possibilities. In this paper we investigate, in which situations such short lists are most effective and how they should be applied to improve the decoding performance. We present a decoding method for a simple concatenated scheme, in which we create lists by the decoder of a binary inner code and apply them to the q-ary symbols of an outer Reed-Solomon code

Interleaved Reed-Solomon codes allow the correction of errors beyond half the minimum code distance if the errors are not distributed independently in the received signal but occur in bursts. Therefore, these codes are mainly considered for applications in channels, that cause correlated error patterns, i.e., error bursts. However, they can also be quite interesting for memoryless channels causing independent random errors, if they are applied in concatenated code designs. We present such concatenated codes with several outer Reed-Solomon codewords and demonstrate the gain, that can be obtained by interleaved Reed-Solomon decoding in comparison to independently decoding the several words of the underlying Reed-Solomon codes.

A polyalphabetic (or mixed) block code is a set of codewords of finite length, where every symbol of a codeword belongs to its own alphabet. In contrast to previous publications we consider a general case, where we do not assume any algebraic structure of the alphabets and the codes. Upper and lower bounds on the cardinality of a polyalphabetic code with given Hamming distance are obtained. Some constructions of polyalphabetic codes are suggested based on known codes. Encoding and decoding of the polyalphabetic codes, obtained in this way, can be done using encoding and decoding algorithms for the mother code. Using this constructions, codes are obtained, that reach the upper Singleton type bound.

Serially concatenated trellis coded modulation (SCTCM) yield both power and bandwidth efficient transmission systems. In this paper the choice of the inner trellis code as well as the outer convolutional code based on the so-called slope is discussed.

We investigate a decision feedback strategy for convolutional codes which is based on a sliding window decoding procedure and a threshold test as decision rule. For this purpose, we introduce the burst distance spectrum of a convolutional code and derive asymptotic bounds for the ensemble of periodically time-varying convolutional codes. These results are helpful for the asymptotic analysis of the decision feedback scheme. Unit memory codes are particularly suited for such a transmission scheme. For these codes, the decoding procedure is reduced to the decoding of block codes with lengths in the order of the overall constraint length of the convolutional code. This leads to a significantly smaller decoding complexity compared with other known decision rules. Whereas the achievable asymptotic performance is close to the best known bounds. For low rates, our results even improve these bounds.

This paper describes the hierarchical woven coded CPFSK (hWCCPFSK), is a serial concatenation of different outer convolutional codes and inner continuous phase frequency shift keying (CPFSK). Classical woven coded CPFSK (cWCCPFSK) has identical outer convolutional codes. We show that with a proper choice of the outer codes, hWCCPFSK has better decoding behaviour but cWCCPFSK has larger free distance. Hence, hWCCPFSK performes better in the waterfall region of the bit error rate curves, while cWCCPFSK is better in the error floor region.

To find the best path in a trellis, the Viterbi algorithm can be used. We present an algorithm to find not only the best, but a sorted list of the /spl lscr/ best paths. Our algorithm is based on the Viterbi algorithm and iteratively applies a back-tracing procedure to find the /spl lscr/ best paths.

We present a new concatenated code construction. The resulting codes can be viewed as intermediate between parallel and serially concatenated convolutional codes. Proper partitioning of the outer code sequence provides a new degree of freedom for code design. Various methods are considered to analyze code properties.

An iterative decoding scheme for woven convolutional codes is presented. It operates in a window sliding over the received sequence. This exploits the nature of convolutional codewords as infinite sequences and reflects the concept of considering convolutional encoding and decoding as a continuous process. The decoder is analyzed in terms of decoding delay and decoding complexity. Its basic building block is a symbol-by-symbol a posteriori probability (APP) decoder for convolutional codes, which is a windowed variant of the well-known Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm. Additional interleaving for the woven constructions is introduced by employing convolutional scramblers. It is shown that row-wise random interleaving preserves the lower bound on the free distance of the original woven constructions. Based on the properties of the interleavers, new lower bounds on the free distance of woven constructions with both outer warp and inner warp are derived. Simulation results for woven convolutional codes with and without additional interleaving are presented.

Nested convolutional codes are a set of convolutional codes that is derived from a given generator matrix. The structural properties of nested convolutional codes and nested generator matrices are studied. A method to construct the set of all minimal (rational) generator matrices of a given convolutional code is presented. As an example, two different sets of nested convolutional codes are derived from two equivalent minimal generator matrices. The significant difference in their free-distance profiles emphasizes the importance of being careful when selecting the generator matrices that determine the nested convolutional codes. As an application of nested convolutional codes, woven codes with outer warp, and inner nested convolutional codes are considered. The free-distance profile of the inner generator matrix is shown to be an important design tool.

In this paper, we investigate the applicability of the Plotkin code construction method to arbitrary finite sets, particularly complex valued modulation alphabets. Furthermore, we derive a recursive soft-in/soft-out decoding algorithm for these code constructions. The purpose is to have an encoding/decoding scheme available, which uses elements of finite sets-especially the complex valued elements of modulation alphabets-directly as information symbols. Simulations for some simple code constructions show the flexibility and performance of that codes and the proposed decoding algorithm.

The critical design criterion for space-time codes in asymptotically good channels is the minimum rank between codeword pairs. Rank codes are a two-dimensional matrix code construction where by the rank is the metric of merit. We look at the application of rank codes to space-time code design. In particular, we provide construction methods of full-rank codes over different complex signal constellations, for arbitrary numbers of antennas, and codeword periods. We also derive a Singleton-type bound on the rate of a code for the rank metric, and we show that rank codes satisfy this bound with equality.

We consider convolutional and block encoding schemes which are variations of woven codes with outer warp. We propose methods to evaluate the distance characteristics of the considered codes on the basis of the active distances of the component codes. With this analytical bounding technique, we derived lower bounds on the minimum (or free) distance of woven convolutional codes, woven block codes, serially concatenated codes, and woven turbo codes. Next, we show that the lower bound on the minimum distance can be improved if we use designed interleaving with unique permutation functions in each row of the warp of the woven encoder. Finally, with the help of simulations, we get upper bounds on the minimum distance for some particular codes and then investigate their performance in the Gaussian channel. Throughout this paper, we compare all considered encoding schemes by means of examples, which illustrate their distance properties.

We show that the generator matrix of a generalized concatenated code (GCC code) of order L consists of L submatrices, where the lth submatrix is the Kronecker product of the generator matrices of the lth inner code and the lth outer code. In a similar way we show that the parity-check matrix of a generalized error location code (GEL code) of order L consists of L submatrices, where the lth submatrix is the Gronecker product of the parity-check matrices of the lth inner code and the lth outer code. Then we use these defining matrices to show that for any GCC code there exists an equivalent GEL code and vice versa.

Iterative decoding methods have gained interest, initiated by the results of the so-called "turbo" codes. The theoretical description of this decoding, however, seems to be difficult. Therefore, we study the iterative decoding of block codes. First, we discuss the iterative decoding algorithms developed by Gallager (1962), Battail et al. (1979), and Hagenauer et al. (1996). Based on their results, we propose a decoding algorithm which only uses parity check vectors of minimum weight. We give the relation of this iterative decoding to one-step majority-logic decoding, and interpret it as gradient optimization. It is shown that the used parity check set defines the region where the iterative decoding decides on a particular codeword. We make plausible that, in almost all cases, the iterative decoding converges to a codeword after some iterations. We derive a computationally efficient implementation using the minimal trellis representing the used parity check set. Simulations illustrate that our algorithm gives results close to soft decision maximum likelihood (SDML) decoding for many code classes like BCH codes. Reed-Muller codes, quadratic residue codes, double circulant codes, and cyclic finite geometry codes. We also present simulation results for product codes and parallel concatenated codes based on block codes.

A novel construction for encoded tamed frequency modulation (TFM) is introduced which is based on the principles of generalized concatenation. The inner TFM is partitioned into nested subsystems which increases the free Euclidean distances. In order to obtain a large distance among the nested TFM subsystems, the scrambler matrices have to be computed which transfer the original TFM into the equivalent TFM with better partitioning properties. Then outer convolutional codes with different error-correcting capabilities are used to protect the partitioning. The new concatenated and generalized concatenated constructions were simulated in an additive white Gaussian noise channel. A multistep decoding algorithm based on soft-output demodulation was used. We present various simulation results which show a significant coding gain in comparison with the best known trellis codes having the same trellis state complexity.

A novel construction method is presented for array codes correcting a single rectangular error cluster of size b/sub 1//spl times/b/sub 2/ or less. Encoding is done in such a way that parity check symbols are calculated row-or columnwise which are a word of a one-dimensional code correcting a phased burst. These parity check symbols are not transmitted but can be calculated by the receiver. Corresponding decoding algorithms are given. A code is constructed with maximum size n/sub 1/=b/sub 1/2/sup b2/, n/sub 2/=b/sub 2/2/sup b1/, and r=3b/sub 1/b/sub 2/ redundancy symbols which is close to the generalized Singleton bound r/spl ges/2b/sub 1/b/sub 2/. Its encoding and decoding complexity are low.

We study the performance of MC-FDMA when applied in mobile communications. We describe two MC-FDMA strategies with control from the base station, telling the users which channels to use. Then we describe a strategy without control from the base station, where the users randomly select their subchannels. For this strategy we describe a joint-detection decoding algorithm with interference cancellation which increases the performance. We compute the optimum number of selected subchannels per user for the random strategy, and describe an adaptive optimum random strategy. In order to compare the different strategies we compute the user capacity, that is the amount of information per transmitted block. Since the number of users in cities is bigger, we consider typical urban channels (TUX) for our simulations.

Consider the transmission of codewords over a channel which introduces dependent errors. Thinking of two-dimensional codewords, such errors can be viewed as blots of a particular shape on the codeword. For such blots of errors the combinatorial metric was introduced by Gabidulin (1971) and it was shown that a code with distance d in combinatorial metric can correct d/2 blots. We propose an universal Singleton-type upper bound on the rate R of a blot-correcting code with the distance d in arbitrary combinatorial metric. The rate is bounded by R/spl les/1-(d-1)/D, where D is the maximum possible distance between two words in this metric.

Simulation in Information Technology is a course on system simulation that is offered by the Department of Information Technology to graduate students which are majoring in communications engineering. The course imparts a fundamental knowledge of simulation tools and of mobile communication systems. The simulation tool which is used in the course is COSSAP (Communication Systems Simulation and Analysis Package) and the considered communication system is GSM (Global System for Mobile communications). The authors give an introduction into COSSAP, into GSM and especially into the course structure. In addition, some simulation results are given, i.e. the improvement of soft decision decoding versus hard decision decoding.

Constructs Reed-Muller codes by generalized multiple concatenation of binary block codes of length 2. As a consequence of this construction, a new decoding procedure is derived that uses soft-decision information. The algorithm is designed for low decoding complexity and is applicable to all Reed-Muller codes. It gives better decoding performance than soft-decision bounded-distance decoding. Its decoding complexity is much lower than that of maximum-likelihood trellis decoding of Reed-Muller codes, especially for long codes.>

A decoding algorithm for linear codes that uses the minimum weight words of the dual code as parity checks is defined. This algorithm is able to correct beyond the half minimum distance and has the capability of including soft-decision decoding. Results on applying this algorithm to quadratic residue (QR) codes, BCH codes, and the Golay codes (with and without soft-decision decoding) are presented.