Digital communications systems and digital storage systems (e.g., hard disk drives) are similar from the perspective of extracting the original (transmitted or stored) bits from the received signal or from the readback signal. In the case of communications channels, the digital information is transferred from one location to another location, but at the same time (perhaps with a small transmission delay), whereas in storage channels, the information is transferred from one time to a later time, but at the same location. The goal in both cases is to retrieve the original bits as accurately as possible in the presence of impairments such as noise and inter-symbol interference (ISI).
One method for improving the accuracy of the retrieved digital information involves using error correcting codes (ECCs). ECCs typically use parity bits to introduce redundancy into the signal prior to transmission or storage. Such redundancy is subsequently used to decode the encoded information. In order to demonstrate the typical manner in which parity bits are currently used for this purpose, an example of a known digital storage system and its operations will be described with reference to FIGS. 1-5.
FIG. 1 illustrates a block diagram of a known digital storage system 1 that uses parity bits to encode information prior to storing the information. The digital storage system 1 includes an encoder 2 that encodes information bits by pseudo-randomly interleaving parity bits throughout the information bits. The encoder 2 is typically a two-dimensional product code (TPC) encoder. The encoded information bits are subsequently read out of the recording channel 3. The recording channel 3 typically includes physical and electrical components (not shown), such as the read/write head, the read/write head armature, the recording media, the pre-amplifier, etc.
As encoded information bits are read out of the recording channel 3, they are processed by a channel detector 4 that performs an algorithm to detect bits. The detector 4 is typically a hard Viterbi detector that produces hard decisions (i.e., a decision that a bit is either a 1 or a 0) or a soft-output Viterbi algorithm (SOVA) detector that produces hard decisions and reliability estimates (i.e., respective estimates as to the reliability of the respective hard decisions). The soft and hard outputs of the channel detector 4 are received by a channel decoder 5, which deinterleaves the parity bits and decodes the bit sequence using the soft and hard outputs from the SOVA channel detector 4.
For this example, it will be assumed that a particular sequence of original information bits, uk=010110, is to be stored in the recording channel 3. This particular sequence is represented by the 3×2 table 11 shown in FIG. 2A. The sequence is encoded by the encoder 2 to produce a codeword. Assuming that the encoder 2 is a two-dimensional product (TPC) encoder, a parity bit is added to each row and to each column of the 3×2 table 11 to produce an even parity code (i.e., each column and each row contains an even number of 1's). The resulting 4×3 table 12 is shown in FIG. 2B. For this example, it will be assumed that each column in the 4×3 table 12 corresponds to a single parity codeword. However, this is not normally the case. As stated above, the parity bits are typically pseudo-randomly interleaved throughout the original information bits. For ease of explanation, the parity bits are shown as simply added to each row and column of table 11 in such a way that each 4-bit column of table 12 is provided with even parity.
The resulting codeword ck=010111001001 is recorded in the recording channel 3. The signal xk read from the recording channel 3 is typically corrupted by noise, nk, such as additive Gaussian noise, for example, which produces samples yk that are received by the channel detector 4. The channel detector 4, which will be assumed to be a SOVA detector for this example, receives the samples yk and produces hard decisions and corresponding soft reliability estimates. This information is then processed by the decoder 5 to produce the recovered information bits.
The recording channel 3 may be modeled as a very simple partial response one-delay (1-D) element channel, as shown in FIG. 3. The recording channel 3 modeled as a 1-D element channel 20 has an input 21, an output 22, a summer 23 and a delay element 24. The summer 23 sums the bit stored in the delay element 24 with the current bit in the ck sequence to produce a current bit in the output sequence xk.
FIG. 4 illustrates a state trellis diagram 30 for the 1-D element channel 20 shown in FIG. 3. The channel model 20 has two states, namely, state 0 and state 1. The channel states depend on the bit stored in the delay element 24. The initial state of the delay element 24 is presumed to be zero. Each of the transition branches 32-35 in the trellis diagram 30 is associated with one input bit and one output bit. For example, “0/1” corresponds to an input bit 1 and an output bit 0. If the state of the delay element 24 is 0 at time k−1 and the channel input bit is 0 at time k−1, then the channel output bit at time k−1 is 0 (i.e., 0+0). Branch 32 of the trellis diagram 30 represents this 0/0 output/input. If the channel input bit at time k−1 is 1 and the state of the delay element 24 is 0 at time k−1 then the channel output bit at time k−1 is 1 (i.e., 1-0). Branch 33 of the trellis diagram 30 represents this 1/1 output/input. If the state of delay element 24 at time k−1 is 1 and the channel input at time k−1 is 0, then the channel output at time k−1 is 0. Branch 34 of the trellis diagram 30 represents this−1/0 output/input. If the state of delay element 24 at time k−1 is 1 and the channel input at time k−1 is 1, then the channel output at time k−1 is 0. Branch 35 of the trellis diagram 30 represents this 0/1 output/input.
FIG. 5 illustrates the 1-D trellis diagram 40 corresponding to the ideal channel output, xk=01-1100-101-101, for the channel input, ck=010111001001, for times k=0 through k=11 for the entire 12-bit sequence shown in FIG. 3. The sequences ck, xk, nk, and yk for this example are listed below in Table 1.
TABLE 1Sequence valuesk01234567891011ck010111001001xk01−1100−101−101nk000−0.60000.50000.2yk01−10.400−10.51−101.2
The SOVA detector 4 determines the maximum likelihood (ML) path that has the minimum distance to the received sequence yk. Assuming the initial state of the delay element is 0, the ML path is made up of branches 41-52 of the trellis 40 shown in FIG. 5. As is well know in the art, the ML path is chosen by selecting the branches that have ideal inputs that are closest to the values of the corresponding yk samples. For example, for yk=0 at time k=0, the chosen branch is the 0/0 branch labeled 41. For yk=1 at time k=1, the chosen branch is the 1/1 branch labeled 42. For yk=−1 at time k=2, the chosen branch is the −1/0 branch labeled 43.
By continuing to perform this algorithm for times k=3 through k=11, the SOVA detector 4 generates an estimated input bit sequence of 010000001001 for times k=1 through k=11. A comparison of this sequence with the original input sequence ck shown in Table 1 shows that the bit decisions made by the SOVA detector 4 for times k=3, k=4 and k=5 do not have the same values as the bits of the ck sequence for those same times. Therefore, although the SOVA detector 4 is reasonably accurate at detecting bits, there is room for improvement.
As stated above with reference to FIG. 1, the decoder 5 receives the hard and soft outputs from the SOVA channel detector 4 and uses this information to decode the bit sequence read from the read channel and recover the original information bits. One known way to improve the accuracy with which bits are detected and decoded is to implement channel detector and decoder hardware that provides for iteration of the data detection and decoding processes. However, this typically involves duplicating detection and decoding logic and memory, which is expensive in terms of hardware and in terms of the amount of area that the hardware consumes on the integrated circuit (IC) in which these components are incorporated.
FIG. 6 illustrates a block diagram of typical detector and decoder hardware 60 configured to provide iteration of the data detection and decoding processes described above with reference to FIGS. 1-5. A first SOVA channel detector 61 processes the bit sequences read from the read channel in the manner described above and generates hard and soft outputs. A first channel decoder, which is represented by the components within the dashed box 62, receives the hard and soft outputs generated by the detector 61. The first channel decoder 62 includes first and second row decoders 63 and 66, respectively, first and second column decoders 64 and 67, respectively, a delay element 65 and summers 68, 69 and 71.
The encoded bits are typically stored in the read channel in a table comprising rows and columns (e.g., table 12 shown in FIG. 2B). The first row decoder 63 receives the hard and soft detector outputs and uses them to decode the rows. The first column decoder 64 receives the hard and soft detector outputs and uses them to decode the columns. The decoders 63 and 64 generate outputs that are combined by summers 68 and 69 with the delayed outputs of the SOVA detector 61, as delayed by the delay element 65. The combination of the outputs of the SOVA detector 61 and the column decoder 64 are then provided to the second row decoder 66. Likewise, the combination of the outputs of the SOVA detector 61 and the first row decoder 63 are provided to the second column decoder 67. The second row and column decoders 66 and 67, respectively, then use this information to decode the rows and columns.
Thus, the second row decoder 66 uses information generated by the first column decoder 64 to further decode the rows and the second column decoder 67 uses information generated by the first row decoder 63 to further decode the rows. This type of iteration in the decoder requires both column and row decoders because each uses information from the other to make decoding decisions.
In addition, there is also iteration between the detector and decoder processes. As shown in FIG. 6, the outputs of the second row and column decoders 66 and 67 are combined by summer 71 and provided to a second SOVA channel detector 72 and to a delay element 73. The second SOVA detector 72 also receives the same input to the first SOVA detector 61 delayed by delay element 75. The second SOVA detector 72 generates soft and hard outputs that are combined by summer 74 with the delayed combined outputs of the row and column decoders 66 and 67, respectively, as delayed by delay element 73. This information is then provided to a second channel decoder, which is represented by dashed box 76.
The second channel decoder 76 processes the information received by it in the same manner in which the first channel decoder 62 processes information. The second channel decoder 76 includes components 83, 84, 85, 86, 87, 88, 89 and 91 that are identical to components 63, 64, 65, 66, 67, 68, 69 and 71, respectively. In addition, the second channel decoder 76 includes a delay element 92 that provides a time delay that is equal to the time delay provided by delay element 85. The outputs of the row and column decoders 86 and 87 of the second channel decoder 76 are combined by summer 91 with the delayed input to the second channel decoder 76. The result is the recovered original information bits.
While iteration of the type performed by the hardware configuration 60 shown in FIG. 6 improves data detection and decoding accuracy, it requires a large amount of processing logic and memory. Consequently, the iterative hardware configuration 60 consumes a relatively large amount of area on the IC in which the hardware configuration 60 is implemented. The hardware configuration 60 is also relatively inefficient in terms of power consumption. In addition, all of the iterative processing takes a relatively large amount of time to be performed, which decreases the overall speed of the system.
A need exists for a system for detecting and decoding data that has reduced hardware complexity and thus is more efficient in terms of the amount of area required for implementation and in terms of the amount of power it consumes. A need also exists for a system for detecting and decoding data that has reduced hardware complexity and improved performance relative to known systems for detecting and decoding data.