Statistical machine translation is a relatively new approach to the long-standing problem of translating human languages by computer. Current statistical techniques uncover translation rules from bilingual training te...
详细信息
Statistical machine translation is a relatively new approach to the long-standing problem of translating human languages by computer. Current statistical techniques uncover translation rules from bilingual training texts and use those rules to translate new tests. The general architecture is the source-channel model: an English string is statistically generated (source), then statistically transformed into French (channel). In order to translate (or "decode") a French string, we look for the most likely English source. We show that for the simplest form of statistical models, this problem is NP-complete, i.e., probably exponential in the length of the observed sentence. We trace this complexity to factors not present in other decoding problems.
An important goal in communication theory is to construct good minimum squared Euclidean distance (MSED) codes for transmission over additive white Gaussian noise (AWGN) channels. In this paper, a new construction met...
详细信息
An important goal in communication theory is to construct good minimum squared Euclidean distance (MSED) codes for transmission over additive white Gaussian noise (AWGN) channels. In this paper, a new construction method for the M-ary phase-shift-keyed (M-PSK) codes over the ring structure Z(M) the ring of integers module M, with a good minimum Euclidean distance, is proposed. The proposed codes are linear when multiple coset leaders are considered. The characteristics and performance levels of the newly constructed codes are analyzed for code length up to n less than or equal to 8. It is found that the proposed codes compare favorably with Piret's codes and Graeffe's method codes on Gaussian channels in terms of decoding complexity, coding gain, and error performance.
作者：
Kamiya, NNEC Corp Ltd
C&C Media Res Labs Miyamae Ku Kawasaki Kanagawa 2168555 Japan
In this paper, three algebraic soft-decision decoding algorithms are presented for binary Bose-Chaudhuri-Hocquengham (BCH) codes. Two of these algorithms are based on the bounded distance (BD) +1 generalized minimum-d...
详细信息
In this paper, three algebraic soft-decision decoding algorithms are presented for binary Bose-Chaudhuri-Hocquengham (BCH) codes. Two of these algorithms are based on the bounded distance (BD) +1 generalized minimum-distance (GMD) decoding presented by Berlekamp, and the other is based on Chase decoding. A simple algebraic algorithm is first introduced, and it forms a common basis for the decoding algorithms presented here. Next, efficient ED +1 GMD and ED +2 GMD decoding algorithms are presented. It is shown that, for binary BCH codes with odd designed-minimum-distance d and length n, both the ED +1 GMD and the ED +2 GMD decoding algorithms can be performed with complexity O(nd), The error performance of these decoding algorithms is shown to be significantly superior to that of conventional GMD decoding by computer simulation. Finally, an efficient algorithm is presented for Chase decoding of binary BCH codes. Like a one-pass GMD decoding algorithm, this algorithm produces all necessary error-locator polynomials for Chase decoding in one run.
In this correspondence, the error exponents and decoding complexity of binary woven convolutional codes with outer and inner warp are studied. It is shown that for both constructions an error probability that is expon...
详细信息
In this correspondence, the error exponents and decoding complexity of binary woven convolutional codes with outer and inner warp are studied. It is shown that for both constructions an error probability that is exponentially decreasing with the memory of the woven convolutional codes can be achieved with a nonexponentially increasing decoding complexity. Furthermore, the error exponent for woven convolutional codes with inner warp is larger than the one for woven convolutional codes with outer warp.
A family of modified turbo codes with SPC precoding is presented. Compared viith standard turbo codes, the new scheme results in considerably lower decoding cost yet can achieve nearly the same performance.
A family of modified turbo codes with SPC precoding is presented. Compared viith standard turbo codes, the new scheme results in considerably lower decoding cost yet can achieve nearly the same performance.
Block-coded modulation (BCM) combines bandwidth-efficient modulation techniques with error-correction capabilities to allow efficient data transmission over mobile communication channels. The main shortcoming of BCM i...
详细信息
Block-coded modulation (BCM) combines bandwidth-efficient modulation techniques with error-correction capabilities to allow efficient data transmission over mobile communication channels. The main shortcoming of BCM is the complex decoding process for which, until today, mainly suboptimum decoding methods are used, because existing approaches for trellis decoders are limited to a small subset of possible BCM schemes. The authors address this shortcoming by introducing a new technique for the construction of trellis decoders for arbitrary BCM schemes. This technique is based on a new approach for the calculation of the trellis state vector and a computationally efficient recursive method for the construction of the trellis. A large number of simulation results for BCM schemes with various QAM constellations are presented, and comparisons in terms of performance and decoding complexity allow the formulation of guidelines for the choice of efficient coding schemes.
In this correspondence the error exponent and the decoding complexity of binary woven convolutional codes with outer warp and with binary convolutional codes as outer and inner codes are studied. It is shown that an e...
详细信息
In this correspondence the error exponent and the decoding complexity of binary woven convolutional codes with outer warp and with binary convolutional codes as outer and inner codes are studied. It is shown that an error probability that is exponentially decreasing with the product of the outer and inner code memories can be achieved with a nonexponentially increasing decoding complexity.
Upper and lower bounds are derived for the decoding complexity of a general lattice L. The bounds are in terms of the dimension n and the coding gain gamma of L, and are obtained based on a decoding algorithm Which is...
详细信息
Upper and lower bounds are derived for the decoding complexity of a general lattice L. The bounds are in terms of the dimension n and the coding gain gamma of L, and are obtained based on a decoding algorithm Which is an improved version of Kannan's method, The tatter is currently the fastest known method for the decoding of a general lattice, For the decoding of a point x, the proposed algorithm recursively searches inside an n-dimensional rectangular parallelepiped (cube), centered at x, With its edges along the Gram-Schmidt vectors of a proper basis of L. We call algorithms of this type recursive cube search (RCS) algorithms. It is shown that Kannan's algorithm also belongs to this category, The complexity of RCS algorithms is measured in terms of the number of lattice points that need to be examined before a decision is made, To tighten the upper bound on the complexity, We select a lattice basis which is reduced in the sense of Korkin-Zolotarev, It is shown that for any selected basis, the decoding complexity (using RCS algorithms) of any sequence of lattices with possible application in communications (gamma greater than or equal to 1) grows at least exponentially with n and gamma. It is observed that the densest lattices, and almost all of the lattices used in communications, e.g., Barnes-Wall lattices and the Leech lattice, have equal successive minima (ESR I). For the decoding complexity of ESM lattices, a tighter upper bound and a stronger loner bound result are derived.
In this partially tutorial paper, we examine minimal trellis representations of linear block codes and analyze several measures of trellis complexity: maximum state and edge dimensions, total span length, and total ve...
详细信息
In this partially tutorial paper, we examine minimal trellis representations of linear block codes and analyze several measures of trellis complexity: maximum state and edge dimensions, total span length, and total vertices, edges and mergers. We obtain bounds on these complexities as extensions of well-known dimension/length profile (DLP) bounds, Codes meeting these bounds minimize all the complexity measures simultaneously;conversely, a code attaining the bound for total span length, vertices, or edges, must likewise attain it for all the others, We define a notion of ''uniform'' optimality that embraces different domains of optimization, such as different permutations of a code or different codes with the same parameters, and we give examples of uniformly optimal codes and permutations, We also give some conditions that identify certain cases when no code or permutation can meet the bounds, In addition to DLP-based bounds, we derive new inequalities relating one complexity measure to another, which can be used in conjunction with known. bounds on one measure to imply bounds on the others, As an application, we infer new bounds on maximum state and edge complexity and on total vertices and edges from bounds on span lengths.
Cosets of convolutional codes can be used to obtain large free Euclidean distances and short maximum zero-run lengths at the output of the 1 - D partial-response channel (PRC). We present a new soft-decision decoding ...
详细信息
Cosets of convolutional codes can be used to obtain large free Euclidean distances and short maximum zero-run lengths at the output of the 1 - D partial-response channel (PRC). We present a new soft-decision decoding technique for cosets of convolutional codes on the preceded 1 - D PRC. The decoding technique is especially well suited for cosets of partial unit memory (PUM) convolutional codes. A connection between the decoder trellises for cosets of block codes and PUM codes on the 1 - D PRC is exploited to obtain a small number of operations per decoded information bit. We prove that the new decoding technique needs fewer operations than the Viterbi algorithm for any (n, n - r), r greater than or equal to 1, PUM code coset with n less than or equal to 2(nu-r) where nu is the constraint length. It is also indicated how to prove the same result for other classes of codes. For many of the best known PUM code cosets, the new decoding technique requires both fewer operations per decoded information bit and smaller path memories than the Viterbi algorithm needs for comparable cosets of punctured convolutional codes.
暂无评论