This paper introduces several techniques for minimal trellis construction for degenerate decoding of quantum stabilizer codes, specifically the minimal multi-goal trellis for the cosets of the stabilizer group S in the normalizer group N. The methods include a merging algorithm, a Shannon-product approach, and the BCJR-Wolf method. The study establishes the necessary properties of multi-goal trellises and bounds on the decoding complexity of the minimal multi-goal trellis using the sum-product Viterbi algorithm. The proposed multi-goal trellises decrease the decoding complexity by a factor O(n), where n is the code length.

Embedded image processing applications like multicamera-based object detection or semantic segmentation are often based on Convolutional Neural Networks (CNNs) to provide precise and reliable results. The deployment of CNNs in embedded systems, however, imposes additional constraints such as latency restrictions and limited energy consumption in the sensor platform. These requirements have to be considered during hardware/software co-design of embedded Artifical Intelligence (AI) applications. In addition, the transmission of uncompressed image data from the sensor to a central edge node requires large bandwidth on the link, which must also be taken into account during the design phase.Therefore, we present a simulation toolchain for fast evaluation of hardware-aware CNN partitioning for embedded AI applications. This approach explores an efficient workload distribution between sensor nodes and a central edge node. Neither processing all layers close to the sensor nor transmitting all uncompressed raw data to the edge node is an optimal solution for each use case. Hence, our proposed simulation toolchain evaluates power and performance metrics for each reasonable partitioning point in a CNN. In contrast to the state of the art, our approach does not only consider the neural network architecture. In the evaluation, our simulation toolchain additionally takes into account hardware components such as special accelerators and memories that are implemented in the sensor node.Exemplary, we show the simulation results for three commonly used CNNs in embedded systems. Thereby, we identify advantageous partitioning points regarding inference latency and energy consumption. With the support of the toolchain, we are able to identify three beneficial partitioning points for FCN ResNet-50 and two for GoogLeNet as well as for SqueezeNet V1.1.

Consider the identification (ID) via channels problem, where a receiver decides whether the transmitted identifier is its identifier, rather than decoding it. This model allows to transmit identifiers whose size scales doubly-exponentially in the blocklength, unlike common transmission codes with exponential scaling. Binary constant-weight codes (CWCs) suffice to achieve the ID capacity. Relating parameters of a binary CWC to the minimum distance of a code and using higher-order correlation moments, two upper bounds on binary CWC sizes are proposed. These bounds are also upper bounds on identifier sizes for ID codes constructed by using binary CWCs. We propose two constructions based on optical orthogonal codes (OOCs), which are used in optical multiple access schemes, have constant-weight codewords, and satisfy cyclic cross-correlation and auto-correlation constraints. These constructions are modified and concatenated with outer Reed-Solomon codes to propose new binary CWCs being optimal for ID. Improvements to the finite-parameter performance are shown by using outer codes with larger minimum distance vs. blocklength ratios. We illustrate ID regimes for which our ID code constructions perform significantly better than existing constructions.

We consider a set of security and privacy problems under reliability and storage constraints that can be tackled by using codes and particularly focus on the secret-key agreement problem. Polar subcodes (PSCs) are polar codes (PCs) with dynamically-frozen symbols and have a larger code minimum distance than PCs with only statically-frozen symbols. A randomized nested PSC construction, where the low-rate code is a PSC and the high-rate code is a PC, is proposed for successive cancellation list (SCL) and sequential decoders. This code construction aims to perform lossy compression with side information, i.e., Wyner-Ziv (WZ) coding. Nested PSCs are used in the key agreement problem with physical identifiers and two terminals since WZ-coding constructions significantly improve on Slepian-Wolf coding constructions such as fuzzy extractors. Significant gains in terms of the secret-key vs. storage rate ratio as compared to nested PCs with the same list sizes are illustrated to show that nested PSCs significantly improve on all existing code constructions. The performance of the nested PSCs is shown to improve with larger list sizes, unlike the nested PCs considered. A design procedure to efficiently construct nested PSCs and possible improvements to the nested PSC designs are also provided.

Consider the identification (ID) via channels problem, where a receiver wants to decide whether the transmitted identifier is its identifier, rather than decoding the identifier. This model allows to transmit identifiers whose size scales doubly-exponentially in the blocklength, unlike common transmission (or channel) codes whose size scales exponentially. It suffices to use binary constant-weight codes (CWCs) to achieve the ID capacity. By relating the parameters of a binary CWC to the minimum distance of a code and using higher-order correlation moments, two upper bounds on the binary CWC size are proposed. These bounds are shown to be upper bounds also on the identifier sizes for ID codes constructed by using binary CWCs. We propose two code constructions based on optical orthogonal codes, which are used in optical multiple access schemes, have constant-weight codewords, and satisfy cyclic cross-correlation and autocorrelation constraints. These constructions are modified and concatenated with outer Reed-Solomon codes to propose new binary CWCs optimal for ID. Improvements to the finite-parameter performance of both our and existing code constructions are shown by using outer codes with larger minimum distance vs. blocklength ratios. We also illustrate ID performance regimes for which our ID code constructions perform significantly better than existing constructions.

This paper investigates the decoding of certain Gabidulin codes over a channel with space-symmetric errors. Space-symmetric errors are additive error matrices that have the property that their column and row spaces are equal. We show that for channels restricted to space-symmetric errors, with high probability errors of rank up to$2 (n-k)/3$can be decoded with a Gabidulin code of length$n$and dimension$k$, using a weak-self orthogonal basis as code locators.

Interleaved Reed–Solomon codes admit efficient decoding algorithms which correct burst errors far beyond half the minimum distance in the random errors regime, e.g., by computing a common solution to the Key Equation for each Reed–Solomon code, as described by Schmidt et al. If this decoder does not succeed, it may eitherfailto return a codeword ormiscorrectto an incorrect codeword, and good upper bounds on the fraction of error matrices for which these events occur are known. The decoding algorithm immediately applies to interleaved alternant codes as well, i.e., the subfield subcodes of interleaved Reed–Solomon codes, but the fraction of decodable error matrices differs, since the error is now restricted to a subfield. In this paper, we present new general lower and upper bounds on the fraction of error matrices decodable by Schmidt et al.’s decoding algorithm, thereby making it the only decoding algorithm for interleaved alternant codes for which such bounds are known.

The key agreement problem with biometric or physical identifiers and two terminals for key enrollment and reconstruction is considered. A nested convolutional code construction that performs lossy compression with side information is proposed. Nested convolutional codes are an alternative to nested polar codes and nested random linear codes that achieve all points of the key-leakage-storage regions of the generated-secret and chosen-secret models for long block lengths. Our design uses a convolutional code for vector quantization during enrollment and a subcode of it for error correction during reconstruction. Physical identifiers with small bit error probability are considered to illustrate the gains of the proposed construction. One variant of nested convolutional codes improves on all previous constructions in terms of the key vs. storage rate ratio but it has high complexity. Another variant of nested convolutional codes with lower complexity performs similarly to previously designed nested polar codes. The results suggest that the choice of convolutional or polar codes for key agreement with identifiers depends on the complexity constraints.

Interleaved Reed–Solomon codes admit efficient decoding algorithms which correct burst errors far beyond half the minimum distance in the random errors regime, e.g., by computing a common solution to the Key Equation for each Reed–Solomon code, as described by Schmidt et al. If this decoder does not succeed, it may either fail to return a codeword or miscorrect to an incorrect codeword, and good upper bounds on the fraction of error matrices for which these events occur are known. The decoding algorithm immediately applies to interleaved alternant codes as well, i.e., the subfield subcodes of interleaved Reed–Solomon codes, but the fraction of decodable error matrices differs, since the error is now restricted to a subfield. In this paper, we present new general lower and upper bounds on the fraction of decodable error matrices by Schmidt et al.’s decoding algorithm, thereby making it the only decoding algorithm for interleaved alternant codes for which such bounds are known.

Two new classes of skew codes over a finite field F are proposed, called skew convolutional codes and skew trellis codes. These two classes are defined by, respectively, left or right sub-modules over the skew fields of fractions of skew polynomials over $\mathbb{F}$. The skew convolutional codes can be represented as periodic time-varying ordinary convolutional codes. The skew trellis codes are in general nonlinear over $\mathbb{F}$. Every code from both classes has a code trellis and can be decoded by Viterbi or BCJR algorithms.

The two-terminal key agreement problem with biometric or physical identifiers is considered. Two linear code constructions based on Wyner-Ziv coding are developed. The first construction uses random linear codes and achieves all points of the key-leakage-storage regions of the generated-secret and chosen-secret models. The second construction uses nested polar codes for vector quantization during enrollment and for error correction during reconstruction. The simulation results show that the nested polar codes achieve privacy leakage and storage rates that improve on existing code designs. One proposed code achieves a rate tuple that cannot be achieved by existing methods.

We consider subspace codes obtained by lifting L-interleaved [n, k] Gabidulin codes. When used in networks with random linear coding, these codes are able to correct with high probability γ packet insertions and δ packet deletions provided that γ/L + δ ≤ n - k. We propose to use these subspace codes in the so called fountain mode. In this case we do not need to correct deletions and are able to correct with high probability a large number L(n - k) of packet insertions. We present a simplified decoder correcting insertions only.

A new class of folded subspace codes for noncoherent network coding is presented. The codes can correct insertions and deletions beyond the unique decoding radius for any code rate R ∈ [0, 1]. An efficient interpolation-based decoding algorithm for this code construction is given which allows to correct insertions and deletions up to the normalized radius s (1 - ((1/h + h)/(h - s + 1))R), where h is the folding parameter and s ≤ h is a decoding parameter. The algorithm serves as a list decoder or as a probabilistic unique decoder that outputs a unique solution with high probability. An upper bound on the average list size of (folded) subspace codes and on the decoding failure probability is derived. A major benefit of the decoding scheme is that it enables probabilistic unique decoding up to the list decoding radius.

Random network coding recently attracts attention as a technique to disseminate information in a network. This paper considers a noncoherent multishot network, where the unknown and time-variant network is used several times. In order to create dependence between the different shots, particular convolutional codes in rank metric are used. These codes are so-called (partial) unit memory ((P)UM) codes, i.e., convolutional codes with memory one. First, distance measures for convolutional codes in rank metric are shown and two constructions of (P)UM codes in rank metric based on the generator matrices of maximum rank distance codes are presented. Second, an efficient error-erasure decoding algorithm for these codes is presented. Its guaranteed decoding radius is derived and its complexity is bounded. Finally, it is shown how to apply these codes for error correction in random linear and affine network coding.

We address the problem of increasing the sum rate in a multiple-access system from [1] for small number of users. We suggest an improved signal-code construction in which in case of a small number of users we give more resources to them. For the resulting multiple-access system a lower bound on the relative sum rate is derived. It is shown to be very close to the maximal value of relative sum rate in [1] even for small number of users. The bound is obtained for the case of decoding by exhaustive search. We also suggest reduced-complexity decoding and compare the maximal number of users in this case and in case of decoding by exhaustive search.

We model the decoding of Interleaved Chinese Remainder codes as that of finding a short vector in a Z-lattice. Using the LLL algorithm, we obtain an efficient decoding algorithm, correcting errors beyond the unique decoding bound and having nearly linear complexity. The algorithm can fail with a probability dependent on the number of errors, and we give an upper bound for this. Simulation results indicate that the bound is close to the truth. We apply the proposed decoding algorithm for decoding a single CR code using the idea of “Power” decoding, suggested for Reed-Solomon codes. A combination of these two methods can be used to decode low-rate Interleaved Chinese Remainder codes.

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.

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.

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.

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.

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.

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.

Decisions on sources with memory transmitted over independent channels can be taken by employing trellis calculations. In this paper, it is shown that for a certain class of functions their moments can be computed in the trellis, too. This is done by generalizing the forward/backward recursion known from the BCJR algorithm [1]. In analogy to the symbol probabilities, by introducing a constraint at a certain depth in the trellis we obtain symbol moments. These moments are required for an efficient implementation of the discriminated belief propagation algorithm in [2], and can furthermore be utilized to compute conditional entropies in the trellis. The moment computation algorithm has the same asymptotic complexity as the BCJR algorithm. It is applicable to any commutative semi-ring, thus also providing a generalization of the Viterbi algorithm [3].

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.

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.

The problem of linear shift-register synthesis for a single sequence is solved by the well known Berlekamp-Massey algorithm. The problem of multi-sequence shift-register synthesis is already addressed by Feng and Tzeng. The Feng-Tzeng algorithm can be considered as a generalization of the Berlekamp-Massey algorithm which takes a set of t different sequences of length N and yields a linear shift-register of length l capable of generating all t sequences. However, for the case of multiple sequences of varying length, the Feng-Tzeng algorithm generally does not give the correct solution. We demonstrate this by means of an example and explain, why the Feng-Tzeng algorithm does not work properly in the unequal length case. We propose a modification of the fundamental iterative algorithm (FIA) from Feng and Tzeng, which overcomes the problem with varying length sequences. Based on this algorithm we derive an efficient Berlekamp-Massey like algorithm for solving the multi-sequence shift-register synthesis problem for sequences of varying length

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 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

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.

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 give simple sufficient conditions for a code to be rectangular and show that large families of well-known nonlinear codes are rectangular. These include Hadamard (1893), Levenshtein (1964), Delsarte-Goethals (1975), Kerdock (1972), and Nordstrom-Robinson (1967) codes. Being rectangular, each of these codes has a unique minimal trellis that can be used for soft-decision maximum-likelihood decoding.

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.

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.

A novel trellis design technique for both block and convolutional codes based on the Shannon (1956) product of component block codes is introduced. Using the proposed technique, structured trellises for block and convolutional codes have been designed. It is shown that the designed trellises are minimal and allow reduced complexity Viterbi decoding.

Soft-decision maximum-likelihood decoding of convolutional codes using the Viterbi algorithm with a syndrome trellis is proposed. The parity check matrix of a convolutional code is used to construct the trellis. This trellis is minimal. The number of operations for the decoding of one block of a q-ary rate k/n convolutional code is /spl sim/nq/sup min(k,n-k)/q/sup /spl nu//, where /spl nu/ is the memory size of the code. When the code rate satisfies k/n> 1/2 , the proposed algorithm is simpler than the classical Viterbi algorithm that has complexity /spl sim/nq/sup k/q/sup /spl nu//.>

It is well known that the computational performance of sequential decoding deteriorates greatly when channel errors occur in clusters, as in Gilbert channels. A way of using sequential decoding to exploit the memory of a Gilbert channel that alleviates this problem is presented. A Fano-like metric matched to this channel is used. The method is investigated by simulating sequential decoding utilizing the stack algorithm. The simulations confirm the feasibility of the technique.< >