Unified technique for multi-rate trellis coding and decoding

[0002] 1. Field of the Invention

[0003] The present invention relates to channel coding and decoding in digital communications, particularly high-speed, broadband wireline communications.

[0004] 2. State of the Art

[0005] Channel coding refers to data transformations, performed after source encoding but prior to modulation, that transform source bits into channel bits. Trellis coding is one class of channel coding. Trellis encoders and decoders find widespread use in digital communications, an example of such use being xDSL modems such as HDSL2/G.SHDSL modems. One specific trellis decoder is the Viterbi decoder. Trellis encoders and Viterbi decoders are described, for example, in U.S. Pat. No. 5,457,705, incorporated herein by reference.

[0006] A block diagram of a known data transmission system using a trellis encoder and a Viterbi decoder is shown in FIG. 1 and includes a transmitter comprising convolutional encoder 41, mapping circuit 42 for setting an arrangement of signal points, and 8-PSK (phase shift keying) modulator 43 for phase-modulating which is supplied with 8 signal points generated by 2³bits, and a receiver comprising 8-PSK demodulator 44 and Viterbi decoder 45. Convolutional encoder 41 produces output signal points Y₂, Y₁, Y₀that are mapped into the position shown in FIG. 2 of the accompanying drawings by mapping circuit 42 and then modulated by 8-PSK modulator 43 for transmission to a transmission path. The 8-phase-modulated signal, with noise added during transmission, is demodulated into m-bit soft decision I channel, Q channel (I-ch., Q-ch.) data by 8-PSK demodulator 44. The m-bit soft decision I-ch., Q-ch. data are supplied to Viterbi decoder 45, which produces estimated information data d. Although different data transmission systems use different modulation coding arrangements, some of which may only be one-dimensional instead of two-dimensional (I, Q), the foregoing system may be regarded as exemplary for purposes of the present discussion.

[0007] A block diagram of a typical trellis encoder, or convolutional encoder, is shown in FIG. 3, operation of which will be described. Convolutional encoder 41 is supplied with parallel information bits X₁, X₂that have been converted by serial/parallel converter 101 connected to input terminals 77, 78 of convolutional encoder 41. If the encoding ratio is 2/3, then exclusive-OR gates 85, 86 of convolutional encoder 41 output exclusive-OR of information bits X₁, X₂supplied from input terminals 77, 78 and output signals from shift registers 82, 83, and are stored in respective shift registers 83, 84. At this point, convolutional encoder 41 outputs, as encoded data, output signals Y₁, Y₂as respective information bits X₁, X₂and redundancy bit Y₀from respective output terminals 80, 79, 81. Each time information bits X₁, X₂are inputted, convolutional encoder 41 repeats the above operation and produces output data Y₁, Y₂, Y₀. Output data Y₁, Y₂, Y₀are then mapped into the positions shown in FIG. 2 by mapping circuit 42 of FIG. 1. If there are three input information bits X₁, X₂, X₃and the encoding ratio is 3/4, then, assuming that convolutional encoder 41 is used, convolutional encoder 41 adds redundancy bit Y₀depending on information bits X₁, X₂to information bits X₁, X₂, X₃, and produces 4-bit output data.

[0008] Operation of Viterbi decoder 45 will be described below with reference to FIG. 4, FIG. 5, FIG. 6, and FIG. 7 of the accompanying drawings. FIG. 4 shows the trellis transition of convolutional encoder 41. FIG. 5 shows an ACS (add compare select) circuit composed of adders 50 through 53, comparator 54, and selector 55, and FIG. 6 also shows the ACS circuit. FIG. 7 shows Viterbi decoder 45. In FIG. 7, the m-bit soft decision I ch., Q ch. data decoded from an 8-PSK signal are supplied from input terminals 87, 88, respectively, to branch metric generator 89, which determines likelihood estimates (branch metrics) BM0, BM1, . . . , BM7 between the 8-phase signal points and reception points as shown in FIG. 2. The likelihood estimates BM0, BM1, . . . , BM7 are supplied to ACS circuit 90. To process a 0th state as shown in FIG. 5, branch and path metrics BM0′, PM0, branch and path metrics BM2′, PM2, branch and path metrics BM4′, PM4, and branch and path metrics BM6′, PM6 are added by respective adders 50, 51, 52, 53, and a path metric with maximum likelihood is calculated by comparator 54 and selected by selector 55 as a path metric PM0 on the next occasion. It is assumed that a path that has transited from a 4th state is selected. Upon selection of the path, the history data of the path stored in 4th-state shift register 75 (see FIG. 6) in path memory 91 is shifted to the right into 0th-state shift registers 73 by select signals SEL0 applied to selectors 56, 60, 64, 68, so that 0th-state shift registers 73 store two information bits “01” that are a transition output. Similarly, the above operation is simultaneously carried out with respect to the 1st, 2nd, . . . , 7th states by circuits based on the trellis transition shown in FIG. 4. Each time a received symbol is inputted, path metrics PM0-PM7 with maximum likelihood are detected by maximum likelihood decider 92, and the output signal from the final shift register which represents the state of the most likelihood path is selected by selector 72, thus producing estimates X₂, X₁indicative of estimated decoded bits.

[0009] In order to cover a wide variety of services XDSL standards, such as G.SHDSL, typically specify more than one data rate. Moreover, past experience dictates the need for higher and higher data rates. There are various ways to address this issue of high data rate system with multi-rate functionality. One straightforward approach is to increase the bandwidth of the transmitted signal in proportion to the required data rate. However, this is not a very efficient use of the bandwidth. Another approach is to change the number of bits per symbols, i.e., more bits per symbols for higher data rates. In this approach it is not necessary to increase the bandwidth.

[0010] The difficulty of the variable bits per symbol is that if proper care is not taken, the associated trellis encoding/decoding arrangement can become unduly complex. What is needed is a careful design of the trellis encoding/decoding arrangement so that the multiple bits per symbol for various data rates can be used seamlessly. The present invention addresses this need.

[0011] The present invention, generally speaking, provides efficient trellis encoder/decoder structure that is suitable for accommodating multiple bits per transmitted symbol. On the encoder side for every rate we map the input bits to a transmitted symbol in such a way that the logic required for decoding the encoded bits is virtually the same irrespective of the number of bits per symbol. This results in greatly simplified decoder structure.

[0012] The present invention may be further understood from the following description in conjunction with the appended drawing. In the drawing:

[0013] FIG. 1 is a block diagram of a conventional data transmission system;

[0014] FIG. 2 is a diagram illustrating signal points in the data transmission system of FIG. 1;

[0015] FIG. 3 is a block diagram of a conventional trellis encoder;

[0016] FIG. 4 is a diagram showing a conventional trellis transition with an encoding ratio of 2/3;

[0017] FIG. 5 is a block diagram of a conventional ACS circuit;

[0018] FIG. 6 is a block diagram illustrating a selection sequence of the ACS circuit of FIG. 5;

[0019] FIG. 7 is a block diagram of a conventional Viterbi decoder;

[0020] FIG. 8 is a block diagram of a conventional 16 PAM trellis encoder used in HDSL2 systems;

[0021] FIG. 9 is a block diagram of the convolutional encoder of FIG. 8;

[0022] FIG. 10 is a diagram illustrating a bits-to-symbol mapping of the convolutional encoder of FIG. 8;

[0023] FIG. 11 is a state diagram of the convolutional encoder of FIG. 8;

[0024] FIG. 12 is a diagram further elaborating the state diagram of FIG. 11;

[0025] FIG. 13 is a block diagram of a multi-rate constellation mapper;

[0026] FIG. 14 is a modified bits-to-symbol mapping for 16 PAM allowing for simplified decoding of multi-rate signals;

[0027] FIG. 15 is a bits-to-symbol mapping for 8 PAM;

[0028] FIG. 16 is a bits-to-symbol mapping for 4 PAM;

[0029] FIG. 17 is a bits-to-symbol mapping for 2 PAM;

[0030] FIG. 18 is a block diagram of a Viterbi decoder in accordance with an exemplary embodiment of the present invention;

[0031] FIG. 19 is a partial trellis diagram corresponding to the state diagram of FIG. 11;

[0032] FIG. 20 is a diagram illustrating cosets used by the Branch Metric Generator of FIG. 18;

[0033] FIG. 21 is a diagram illustrating the effect of a truncation operation performed by the Branch Metric Generator of FIG. 18;

[0034] FIG. 22 is a diagram illustrating operation of the ACS block of FIG. 18;

[0035] FIG. 23 is a diagram illustrating a row switching operation performed by the Path Update block of FIG. 18;

[0036] FIG. 24 is a diagram illustrating a traceback table update operation performed by the Path Update block of FIG. 18;

[0037] FIG. 25 is a block diagram of the Decision block of FIG. 18;

[0038] FIG. 26 is a diagram illustrating operation of the Decision block of FIG. 18; and

[0039] FIG. 27 is a block diagram of a more generalized Decision block that may be used in conjunction with a transmitter having a higher than normal data rate.

[0040] Referring now to FIG. 8, a block diagram is shown of a conventional 16 PAM trellis encoder used in HDSL systems. A data binary signal (having a rate of 1.552 Mbps, for example) is input to a serial-to-parallel converter that produces parallel bits x₀, x₁and x₂. Bits x₁and x₂are uncoded bits. Redesignated as y₂and y₃, respectively, they are applied directly to a PAM mapper. Bit x₀is to be encoded and, therefore, applied to a convolutional encoder of the type shown in FIG. 9, for example, comprising a chain of flip-flops, selected output signals of which are exclusive-ORed in the manner indicated. In this manner, the convolutional encoder produces encoded bits y₀and y₁, which are applied to the PAM mapper. The PAM mapper performs a bit-to-symbol mapping and outputs a 1/3 rate signal, e.g., a 517K symbols per second for input rate of 1.552 Mbps.

[0041] Referring to FIG. 10, the bits y₃y₂y₁y₀may be represented by a 12-bit value having a first 5-bit portion including a sign bit a four magnitude bits and a 7-bit zero-filled portion. The number of zero-filled bits determines the precision available for soft decision on the decoder and the overall performance of the trellis encoded modulation scheme.

[0042] Referring now to FIG. 11, a state diagram is shown of the trellis encoder of FIG. 9. Since the trellis encoder has nine flip-flops, it is described by 2⁹=512 states. The transition from one state to the next is governed by the next input bit to the trellis encoder. In FIG. 11, a possible transition is represented by a line from one state to another state labelled with the binary logic value (0 or 1) of the data bit causing the transition and, in parentheses, the logic values of the two output bits produced by the trellis encoder. For example, if the trellis encoder is in state 0 at time n and the next input bit is a 0, the trellis encoder will remain in state 0 at time n+1 and will produce an output of 00. If the trellis encoder is in state 0 at time n and the input next bit is a 1, the trellis encoder will transition to state 1 at time n+1 and will produce an output of 10. As illustrated in FIG. 12, states i and i+256 enter the same next state for the same input bit but different outputs are produced. For example, if the trellis encoder is in state 0+256=256 at time n and the next input bit is a 0, the trellis encoder will transition to state 0 at time n+1 but will produce an output of 10.

[0043] A significant feature of the present system is the ability to use the same decoder structure with signals of different data rates. This ability is made possible in part by adopting a different bits-to-symbol mapping than that used in the prior art. Referring more particularly to FIG. 13, a multi-rate constellation mapper is shown. The constellation mapper has different modes, allowing for different numbers of uncoded bits to be represented in a transmit data symbol. FIG. 14 shows a bits-to-symbol mapping employed by the constellation mapper of FIG. 13 in a 16 PAM mode (two uncoded bits). The interval [−1, 1) is represented, including the values −15/16, −13/16, etc., the denominator being implied rather than explicitly indicated. Beginning at the left hand side of the interval, the values of the symbols y₃y₂y₁y₀progress from zero (0000, mapped to −15/16) to 15 (1110, mapped to −1). As may be seen with reference to FIG. 10, this portion of the mapping is the same as in the prior art. In the right half of the interval, however, this portion of the interval may be imagined as being divided again in half, with the values that would ordinarily appear in one quarter section of the interval being swapped with the values that would ordinarily appear in the other quarter section of the interval. Hence, instead of the symbols values progressing from left to right as 8, 9, 10, etc., they progress as 12, 13, 14, 15, 8, 9, 10, 11. The reason for this mapping will become more apparent from the following description of the decoder structure of the present system.

[0044] Mappings for 8 PAM, 4 PAM and 2 PAM are shown in FIG. 15, FIG. 16, and FIG. 17, respectively. The mappings for 8 PAM and 2 PAM may be considered to be consistent with the prior art mapping of FIG. 10. In the mapping for 4 PAM, however, as compared to what would be the expected mapping based on FIG. 10 (e.g., from left to right, 00xx, 01xx, 10xx, 11xx), the symbols are exchanged between the left and right halves of the interval, and then, within the left half of the interval, the symbols are exchanged again.

[0045] Referring to FIG. 18, a block diagram is shown of a decoder in accordance with an exemplary embodiment. In this embodiment, the input signal to the decoder is a value y_m(which may be represented in signed two's complement form) on the interval [−1, 1), represented in this instance using 12 bits. The output of the decoder is a maximum-likelihood symbol estimate, assuming guassian noise, composed of bit estimates {circumflex over (x)}₂, {circumflex over (x)}₁and {circumflex over (x)}₀, produced by a decision block using a most-recent estimate of the original encoded bit and the most significant five bits of y_m, delayed by 64 symbols period within a buffer. Hence, the trellis decoder has a history depth of 64 symbols.

[0046] The major portion of the work of the decoder is performed by the Branch Metric Generator (BMG), Add-Compare-Select (ACS), and Path Update blocks. Prior to describing an advantageous implementation of these blocks in accordance with one embodiment of the invention, the trellis representing operation of the decoder will be described with reference to FIG. 19. FIG. 19 represents a partial trellis derived from the state diagram of FIG. 11. Each transition from one state to the next within the trellis corresponds to a new value of y_m. Transitions indicated in solid lines are between states shown within the partial trellis diagram of FIG. 19.

[0047] Referring now to FIG. 20, operation of the Branch Metric Generator of FIG. 18 will be described. With two encoded bits, y₁and y₀(FIG. 9), four combinations of y₁y₀are possible, namely 00, 01, 10, 11. Depending on the uncoded bits y₃y₂, the combination y₁y₀=00 may correspond to any of four different symbol values, −15/16, −7/16, 1/16 or 9/16. At the decoder, the minimum distance of the received symbol from this set of points is designated as d₀. (Note that the decimal value of the subscript is the same as the binary value of y₁y₀.) The distances d₁, d₂, and d₃are similarly defined. Each set of points used to compute, respectively, d₀, d₁, d₂, and d₃, defines a “coset.”

[0048] Instead of calculating the distance between the received symbol and all of the points of the constellation, significant efficiency is gained by, for purposes of calculating distances, obtaining a quantity x from y_mby (in the case of 16 PAM) dropping the two most significant bits from y_mas shown in FIG. 21. The effect is to map all of the points in the constellation to a single interval [0, 1/2) The distance d₀is then defined as dis(1/16, x), the distance d₁as dis(3/16, x), etc. As a result, instead of 16 values, the Branch Metric Generator is required to generate for each received symbol only the four values, d₀, d₁, d₂, and d₃. Note in FIG. 21 that the transformation from y_mto x causes symbol values originally within the interval [0, 1/2) to be flipped about the midpoint of the interval. The various symbols mappings of FIG. 14, FIG. 15, FIG. 16 and FIG. 17 account for this occurrence. The values d₀, d₁, d₂, and d₃is squared to achieve optimum performance.

[0049] The transformation from y_mto x varies slightly between modes as shown in Table 1:

[0050] The ACS block of FIG. 18 may be realized as shown diagrammatically in FIG. 22. Storage is provided for two vectors (each of, e.g., dimension of 512). One, J(n−1), is used to stored prior path-weight sums, and the other, J(n), is used to stored new path-weight sums derived from the prior path-weight sums. Each element of the vector J(n) is derived, in accordance with the state diagram of FIG. 11, as the minimum of: 1) the sum of a first selected element of the vector J(n−1) and a selected one of the distances d₀, d₁, d₂, and d₃; and 2) the sum of a second selected element of the vector J(n−1) and a selected one of the distances d₀, d₁, d₂, and d₃. In the case of J₀(n), for example, one observes from the state diagram of FIG. 11 that state 0 may be arrived at from state 0 if the output y₁y₀=00 (to which d₀corresponds) or from state 256 if the output y₁y₀=10 (to which d₂corresponds). The most likely path of the two paths is the one with the minimum path weight. In general, $J_{\varnothing }\left(n\right)=\min \left\{\begin{array}{c}{J}_{i\varnothing ||\rfloor }\left(n-1\right)+d_{{\AA }_{\mathrm{set}}\backslash \varnothing \backslash \epsilon ÷}\equiv C_{\epsilon }\left[i\right]\\ J_{\lfloor \varnothing \left|!+\right|❘⫬->}\left(n-1\right)+d_{{\AA }_{\mathrm{set}}\backslash \varnothing \backslash \bigcap ÷}\equiv C_{\bigcap }\left[i\right]\end{array}\right\}$

[0051] where └X┘ is the largest integer not exceeding X, the floor operation, and where the appropriate D_setvalue (d₀, d₁, d₂, or d₃) in any particular instance is determined by look-up table, for example. Application of the foregoing expression is demonstrated by the following examples:

[0052] J_Σ→∩(n)=min{J_∩i∈(n−1)+d_∩, J_∞Σ(n−1)+d_Σ}

[0053] Since all decisions depend on the relative values, not absolute values, of J_i(n)'s, to avoid saturation, the values of J_i(n) may be adjusted by subtracting the following quantity: $J_{\min }\left(n-1\right)\equiv \underset{i}{\min }{J}_i\left(n-1\right)$

[0054] The Path Update block of FIG. 18 principally comprises a traceback table for storage of the received data sequence history. In an exemplary embodiment, the traceback table requires 512 by 64 bits of storage. A path update operation, in accordance with an exemplary embodiment, consists of 1) a series of row-switching operations; 2) a decision step performed in cooperation with the ACS block; and 3) an update operation in which the oldest column of the traceback table is dropped to accommodate the addition of a new column.

[0055] The new column to be added is calculated as a 512 vector of 0's and 1's, dec[i], in conjunction with the calculation of J(n) of the ACS block, as follows:

[0056] dec[i]=0 if C_∈[i]≦C_∩[i]

[0057] dec[i]=1 if C_∩[i]≦C_∈[i]

[0058] Each bit dec[i] represents the most likely value of the encoded bit x₀assuming the most likely trellis path (of history depth 64 in this example) ending in a particular state. Each row of the traceback table implicitly represents one such path.

[0059] After the new column to be added has been calculated, row switching is performed as illustrated in FIG. 23. As may be appreciated from the preceding discussion, the ith state of the trellis encoder is preceded by either the └i/2┘^thstate or the └i/2┘+256^thstate. Therefore, during traceback table update, the i^throw of the traceback table is replaced by either the └i/2┘^throw or the └i/2┘+256^throw depending on whether dec[i] is 0 or 1, as shown in FIG. 23. For i=10, for example, the 10^throw of the traceback table is replaced by the 5th row if dec[10]=0, else by the 261^strow if dec[10]=1.

[0060] Following row switching, a decision bit, {circumflex over (x)}₀, for the current cycle is produced by using the minimum value of the ACS vector J_i(n) to index into the first column of the traceback table. That is, {circumflex over (x)}₀is the min_J_loc^thbit of the first column of the traceback table after row switching where $\mathrm{min\_j}\mathrm{\_loc}=\arg \underset{i}{\min }{J}_i\left(n\right)$

[0061] After the decision bit has been produced, the traceback table is updated by dropping the first column and adding a new last column computed along with the vector J_i(n) as previously described. Update of the traceback table is illustrated in FIG. 24.

[0062] The Decision block of FIG. 18 is shown in greater detail in FIG. 25. The decision bit {circumflex over (x)}₀is output directly. Although the uncoded bits {circumflex over (x)}₁and {circumflex over (x)}₂could be estimated directly from y_m, greater accuracy may be obtained by passing the decision bit {circumflex over (x)}₀through an identical trellis encoder as used at the transmit side to produce estimates of ŷ₀and ŷ₁. Decision logic uses these estimates together with y_mto estimate the uncoded bits {circumflex over (x)}₁and {circumflex over (x)}₂.

[0063] Operation of the decision logic of FIG. 25 is illustrated in FIG. 26. Different levels are used by the decision logic depending on the estimates of ŷ₀and ŷ₁. The significance of using different levels may be appreciated with reference to FIG. 18. Ignoring y₀and y₁, distinguishing between different combinations of y₂and y₃requires accurately resolving the signal to within ½ the symbol interval, e.g., ½ ({fraction (2/16)})={fraction (1/16)}. Identical combinations of y₀and y₁, however, occur at a much wider interval, e.g., 4 symbol intervals. By using decision levels equidistant from identical combinations of y₀and y₁, the required precision is only ½ ({fraction (8/16)})={fraction (4/16)}. Greater accuracy therefore results.

[0064] The efficient structure of the present decoder lends itself to more dense constellations, allowing for the possibility of increasing the transmit data rate by increasing the number of uncoded bits. In the example of HDSL2/G.SHDSL, for example, the number of uncoded bits may be increased by 1, 2, etc., resulting in 32 PAM, 64 PAM, etc. A description of how such higher data rates may be achieved is set forth in Appendix A.

[0065] A block diagram of a more generalized Decision block allowing for multi-rate capabilities is shown in FIG. 27. The Decision block, which may be used with 4, 8, 16, 32 or 64 PAM signals, receives one additional input bit, y₅, and produces up to two additional output bits, {circumflex over (x)}₃and {circumflex over (x)}₄. A mode signal causes the decision logic to operate in accordance with the desired mode.

[0066] It will be appreciated by those of ordinary skill in the art that the invention can be embodied in other specific forms without departing from the spirit or essential character thereof. The presently disclosed embodiments are therefore considered in all respects to be illustrative and not restrictive. The scope of the invention is indicated by the appended claims rather than the foregoing description, and all changes which come within the meaning and range of equivalents thereof are intended to be embraced therein.