Low power viterbi decoder using a novel register-exchange architecture

An apparatus and method of reducing power dissipation in a register exchange implementation of a Viterbi decoder used in a digital receiver or mass-storage system without degrading the bit error rate of the decoder, by selectively inhibiting data samples in the Viterbi decoder's register memory from being shifted if the data samples have converged to a single value. FIFO memories keep track of what data samples have converged, the order of the samples, and the converged data value, thereby keeping the decoded data in the FIFO synchronized with data continuing to be shifted through the register memory.

FIELD OF THE INVENTION

This invention relates to data communication systems and mass-storage systems and, more particularly, to apparatus and methods for implementing a Viterbi decoder in said systems.

BACKGROUND OF THE INVENTION

Convolutional codes, used for encoding data for transmission or for storage, are used in high-performance digital communication systems, such as cellular telephone systems, and high areal data density magnetic mass-storage systems, such as hard-disk drives. Recovery of the encoded data after transmission or from a magnetic disk system falls to a type of decoder that implements a form of the Viterbi algorithm (VA), referred to generally as a Viterbi decoder (VD). The Viterbi decoder is a complex device that, without high-density very large-scale integrated circuit (VLSI) technology to implement the Viterbi decoder, modern digital cellular telephones, and battery operated computers and mp3 players with hard-disk drives would not be practical. For a detailed description of the Viterbi algorithm, see “Viterbi Algorithm,” by G. Forney, Jr.,Proceedings of the IEEE, vol. 61, no. 3, pp. 268-278, March 1973, hereby incorporated by reference in its entirety.

VDs are also widely used to detect data in the presence of intersymbol interference (ISI), such as in mass-storage systems and bandwidth-limited high-speed communication channels. See “Maximum-Likelihood Sequence Estimation of Digital Sequences in the Presence of Intersymbol Interference,” by G. Forney, Jr.,IEEE Transactions on Information Theory, Vol. IT-18, No. 3, pp. 363-378, May 1972, hereby incorporated by reference in its entirety.

There are two basic forms of the VA: 1) trace-back (TB) and 2) register-exchange (RE). Both algorithms produce “decoded” data based on a probabilistic estimation of received data symbols by knowing a priori the convolution code used to encode the data. The TB version, which retraces the data estimates back in time to find the most likely sequence (path) of encoding for a given received data symbol, allows for small, power efficient VD implementations at the cost of slow speed. The RE version (referred to herein as the RE architecture), which processes a predetermined number of data estimates in parallel such that the estimates merge to a most likely value, is the fastest, least latent, VD implementation. The RE architecture uses commonly clocked flip-flop registers instead of area-efficient random-access memories. Concomitant with the low latency is high power dissipation because all the registers are clocked simultaneously with each clock cycle. It is understood that, for purposes here, the foregoing descriptions of the various forms of VA and the implementations thereof are greatly simplified. For a more detailed description of the TB and RE forms of the VA, see “A 500-Mb/s Soft-Output Viterbi Decoder,” by Yeo et al.,IEEE Journal of Solid-State Circuits, Vol. 38, No. 7, pp. 1234-1241, July 2003, and “High-Speed VLSI Architectures for Soft-Output Viterbi Decoding,” by O. Joeressen et al.,International Conference on Application Specific Array Processors, pp. 373-384, 1992, both of which are hereby incorporated by reference in their entirety.

For many low-power applications, a VD implementing the TB algorithm cannot tolerate the long latency inherent in the algorithm. It is therefore desirable to provide a VD implementing the RE algorithm but with lower power dissipation.

SUMMARY OF THE INVENTION

In one embodiment of the invention, an apparatus, such as a disk drive read channel or digital receiver, includes a Viterbi decoder that has first and second memories that store survivor state data of the decoder, an equality detector, first and second FIFO memories, and a multiplexer. The first memory has an input and an output, the second memory has an input and an output, the input of the second memory coupling to the output of the first memory. The equality detector has an output and an input, the input coupling to the output of the first memory. The first FIFO memory has an input and an output, the input couples to the output of the equality detector. The second FIFO memory has an input and an output, the input coupling to the input of the second memory. The first multiplexer has two inputs, a select input, and an output, a first one of the two inputs couples to the output of the second FIFO, a second one of the two inputs couples to the output of the second memory, and the select input couples to the output of the first FIFO. The output of the first multiplexer is an output of the Viterbi decoder.

In an alternative embodiment, a method for decoding a signal using a Viterbi decoder, comprising the steps of: sequentially shifting survivor state data samples through a first memory to a multi-bit output thereof; sequentially shifting the survivor state data samples from the output of the first memory through a second memory to a multi-bit output thereof; comparing a survivor state data sample at the multi-bit output of the first memory to determine if all the bits have a single value, storing the results of the comparing step and a value of one of the bits of the multi-bit output of the first memory in a FIFO; selectively inhibiting the shifting of the data though the second memory each data sample having bits with the same value; and, selecting, for a given data sample, either a selected bit of the multi-bit output of the second memory or the stored value in the FIFO as a Viterbi decoded data output, depending on the stored comparing step result. The data in the first and second memories and the FIFO are shifted at the same predetermined rate.

Like reference numbers are used throughout the figures to indicate like features. Individual features in the figures may not be drawn to scale.

DETAILED DESCRIPTION

FIG. 1illustrates a conventional “hard decision” VD100implemented using the RE architecture. As described in more detail in “Reconfigurable Viterbi Decoder for Mobile Platform,” by Rasheed, et al.,The7th IFIP International Conference on Mobile and Wireless Communications Networks, Morocco, 2005, (hereby incorporated by reference in its entirety) and the above-referenced paper by Joeressen, et al., the decoder100comprises a Branch Metric Unit (BMU)101which takes received convolutionally encoded data symbols and computes the “distance” (metric) between an ideal symbol and the received symbol based on the code used. The metric is then processed by add-compare-select (ACS) unit102to compute both the path metrics for the received symbols and the survivor data for each received symbol. The survivor data is stored in Path Memory (PM)103(described in more detail below). The path metrics are processed by Best State Select Block104which determines the most likely trellis output node in the PM103having the correct data value. A multiplexer105, controlled by block104, selectively couples one of 2K−1output nodes from PM103as the output of the VD100, where K is a value related to the convolutional code used or, in the case of data detection, K is chosen so that the VD100provides a maximum predetermined bit error rate for a given input signal signal-to-noise ratio, as discussed in more detail below.

FIG. 2is a simplified diagram of a conventional PM103for the RE architecture illustrated inFIG. 1. The PM103comprises columns of commonly clocked registers2011-201L, L being the depth of the PM103. Each column2011-201Lhas a width of 2K−1one-bit registers. In addition to the 2K−1bit-wide columns of registers2011-201L, there are corresponding columns of two-input multiplexers2021-202Lcontrolled by ACS102(FIG. 1) via inputs SEL1-SEL2K−1. Inputs to a given multiplexer come from the immediately preceding columns of registers by corresponding trellis connection logic blocks2031-203L. As is known in the art, interconnections within the logic blocks2031-203Lreplicate the trellis structure of a convolutional code. A selected one of the outputs from the final set of multiplexers202Lare selectively coupled to the output of the VD100by multiplexer105, as described above.

The combination of corresponding, like-subscripted, columns of registers2011-201L, multiplexers2021-202L, and connection logic2031-203L, together comprise a stage2041-204Lof the VD100(e.g.,2012,2022, and2032, form stage2042), each stage performing a step of the VA with each clock cycle. Thus, in this example, there are L stages in the VD100. As is understood by those with ordinary skill in the art, the depth of the PM103, here L, is greater than or equal to 5K, K being the constraint length of the convolutional code used to encode the data. Further, the width of the columns2011-201L, here 2K−1bits, is the number of possible trellis states in the VA.

FIG. 3illustrates the results of repeated simulations of the VD100shown inFIGS. 1 and 2, the VD100implemented as an enhanced partial response class-4 (EPRC4) channel detector for detecting symbols written on a hard disk in a mass-storage system. The simulated 32-state VD100(K=6) is used to perform maximum likelihood sequence estimation on signals “read” from a simulated hard disk as shaped by a EPR4 equalization filter followed by a noise predictive finite-impulse response filter. For a more detailed explanation of how the VA is used in read-channel applications, please refer to the second above-referenced article by G. Forney, Jr., and “Advanced Read Channels for Magnetic Disk Drives,” by Howell et al.,IEEE Transactions on Magnetics, Vol. 30, No. 6, pp. 3807-3812, November 1994, hereby incorporated by reference in its entirety. For each simulation, the VD100is fed the symbols “read” from a hypothetical mass-storage system after the above-stated equalization and noise predictive filters, the symbols having been subjected to the typical distortions, inter-symbol interference, and noise of a typical mass-storage system. The plots shows the percentage of the time that all the output bits of a given stage2041-204Lin the PM103have converged the same value (referred to herein as the data sample converging to a single or the same value), here up to L=30. In this example, for the sixth stage,2046and beyond, all of the output bits have the same value more than 90% of the time. Once the output bits from a given stage have the same value, the value does not change as the data sample passes further through the PM103. Thus, for 90% of the received symbols, processing the data samples beyond six levels deep in the PM103results in no further advantage. However, for the remaining 10% of the received symbols, further processing is needed. Moreover, while it may be tempting to take the data value from the output of the sixth stage as the output of the VD100, there may be earlier-received symbol data still being processed in deeper levels within the PM103, which may result in data being decoded out of order. At the same time, further processing of symbol data that has converged to a single value wastes power since the data continues to be passed through the PM103by clocking all the remaining registers until reaching multiplexer105and passed out of the VD100.

Briefly and in accordance with the invention, to reduce the power consumption of the VD100, the clock signal to register columns in PM103are selectively disabled when a data sample in a preceding stage has converged to a single value. As illustrated inFIG. 4, an exemplary embodiment of the PM403has essentially the same structure as the PM103shown inFIG. 2but is partitioned into two sections401and402, although more than one partition may be used. The sum of the depths of partition401(M stages) and partition402(N stages), is preferably L stages, as discussed above in connection withFIGS. 1 and 2. The depth of partition401, here from stage2041to204M, is chosen so that for a desirable percentage of the time all the output bits from the stage204Min the partition401have the same value. Using the example illustrated inFIG. 3, if the desired percentage is 90% or more, then M=6. The outputs of the multiplexer202Min stage204Mcouple to an equality detector405, which detects if all the output bits of the stage204Mhave the same value, i.e., either all ones or all zeros. First-in-first-out (FIFO) memories406and407are clocked by the same clock (CLOCK) for the register columns in partition402and have the same number of cells in each as there are columns of registers in partition402, i.e., the depth of FIFOs406and407are the same as the depth of partition402, thereby keeping the data flowing through the FIFOs406,407synchronized with data still being processed in the partition402. In this embodiment, FIFO406keeps track of which instances of data in the partition402have converged to a single value and FIFO407keeps track of what the corresponding value is. For each instance where the data converged to a single value, a cell in the FIFO406is a “one,” thereby gating off, or disabling, the clock signal CLOCK from being applied to the corresponding subsequent register column in partition402by gates408. Note that for register column201M+1, the gating of the clock signal CLOCK thereto is controlled by the output of detector405, whereas for subsequent register columns201M+2-201L, the gating is controlled by outputs from the FIFO406.

Optional multiplexer409selects as input to FIFO407either 1) the value of any one of the 2K−1output bits of stage204Mif all the output values of stage204Mare all of a single value as detected by detector405, or 2) the previously loaded data value in the FIFO407if all the output values of stage204Mare not of single value. The “recycling” of a previous value from the FIFO407is a technique to reduce power consumption by minimizing transitions of the cells in FIFO406as it is clocked. However, it is understood that multiplexer409may be removed and the input to FIFO407come directly from any one of the 2K−1outputs of stage204M.

Multiplexer105operates substantially the same as described in connection withFIGS. 1 and 2. As shown, multiplexer105selects one of 2K−1outputs from PM403to produce a one-bit output. Multiplexer410, under control of the output of FIFO406, selectively couples as the output of VD100either the output of multiplexer105or the output of FIFO407.

Operation of the partition401of PM403is substantially the same as the first M stages of PM103, discussed above. For data passing from stage204Minto partition402that are not all of a single value (e.g., are not all “zero” or not all “one” in this example), further processing of that data operates substantially the same as the PM stages of PM103, discussed above. However, for each instance or sample of survivor data from stage204Mhaving values that are all the same (e.g., are all “zero” or “one” in this example), then no further processing of that data sample is needed and the subsequent register columns201M+1-201Ldo not need to be clocked for that data sample. In this case, the FIFOs keep track of the data value in the proper order and selectively disable the corresponding subsequent register columns in partition402. Thus, a mix of data can be simultaneously passing through partition402and through the FIFOs406,407and all the data remains in the proper order when read out from the VD100with each cycle of CLOCK.

In the disclosed embodiment, FIFOs406,407are shown as separate FIFOs, whereas it is understood by those skilled in the art that the two FIFOs may be considered as a single two-bit wide FIFO. Moreover, a skilled artisan may implement the columns of registers2011-201Lin a fast memory and control the reading and writing of the memory in accordance with the invention. In such an embodiment, the partitions401,402may be implemented in separate memories or by logically partitioning one memory into two or more partitions401,402. Further, while the invention is shown implemented as part of an RE architecture, other approaches to VD designs, such as certain combined TB and RE architectures, may advantageously implement the invention. Further, the invention is also applicable to Viterbi decoders that include a “soft-output” in addition to the data output discussed above (referred to generally as SOVA), as described in several of the above-cited references.