[cont. from part 1]
Convolutional Codes
Convolutional codes, sometimes called recurrent codes, differ from block codes in the way data is grouped for coding. Instead of dividing the message data into blocks of k digits and generating a block of n code digits, convolutional codes do not partition data into blocks.
Instead, message digits k are taken a few at a time and used to generate coded digits n, formed not only from those k message digits, but from many previous k digits as well, saved in delay memories. In this way, the coded output contains a history of the previous input data. Such a code is called an (n, k) convolutional code. It uses (N - 1) message blocks with k digits. It has constraint length N blocks (or nN digits) equal to n(m + 1), where m is the number of delays.
Its rate R is k/n.
As with linear block codes, encoding is performed and codewords are transmitted or stored. Upon retrieval, the correction decoder uses syndromes to check codewords for errors. Shift registers can be used to implement the delay memories required in the encoder and decoder. The amount of delay determines the code's constraint length, which is analogous to the block length of a block code. An example of a convolutional encoder is shown in FIG. 13.
There are six delays, thus the constraint length is 14. The other parameters are q = 2, R = 1/2, k = 1, n = 2, and the polynomial is x6 + x5 + x2 + 1. As shown in the diagram, message data passes through the encoder, so that previous bits affect the current coded output.
Another example of a convolutional encoder is shown in FIG. 14A. The upper code is formed from input data with the polynomial x2 + x + 1, and the lower with x2 + 1. The data sequence enters the circuit from the left and is shifted to the right one bit at a time. The two sequences generated from the original sequence with modulo 2 addition are multiplexed to again form a single coded data stream. The resultant code has a memory of two because, in addition to the current input bit, it also acts on the preceding two bits.
For every input bit, there are two output bits; hence the code's rate is 1/2. The constraint length of this code is k = 3.
FIG. 13 A convolutional code encoder with six delay blocks.
FIG. 14 An example of convolutional encoding. A.
Convolutional encoder with k = 3 and R = 1/2. B.
Convolutional code tree diagram. (Viterbi, 1983) A convolutional code can be analyzed with a tree diagram as shown in FIG. 14B. It represents the first four sequences of an infinite tree, with nodes spaced n digits apart and with 2k branches leaving each node. Each branch is an n-digit code block that corresponds to a specific k-digit message block. Any codeword sequence is represented as a path through the tree. For example, the encoded sequence for the previous encoder example can be traced through the tree. If the input bit is a 0, the code symbol is obtained by going up to the next tree branch; if the input is a 1, the code symbol is obtained by going down. The input message thus dictates the path through the tree, each input digit giving one instruction. The sequence of selections at the nodes forms the output codeword. From the previous example, the input 1110 generates the output path 11011001. Upon playback, the data is sequentially decoded and errors can be detected and recovered by comparing all possible transmitted sequences to those actually received. The received sequence is compared to transmitted sequences, branch by branch. The decoding path through the tree is guided by the algorithm, to find the transmitted sequence that most likely gave rise to the received sequence.
FIG. 15 An example of a convolutional code encoder, generating one check
word for every four data words.
Another convolutional code is shown in FIG. 15. Here, the encoder uses four delays, each with a duration of one word. Parity words are generated after every four data words, and each parity word has encoded information derived from the previous eight data words. The constraint length of the code is 14. Convolutional codes are often inexpensive to implement, and perform well under high error conditions. One disadvantage of convolutional codes is error propagation; an error that cannot be fully corrected generates syndromes reflecting this error, and this can introduce errors in subsequent decoding. Convolutional codes are not typically used with recorded data, particularly when editing is required; the discrete nature of block codes makes them more suitable for this. Convolutional codes are more often used in broadcast and wireless applications.
Interleaving
Error correction depends on an algorithm's ability to overcome erroneous data. When the error is sustained, as in the case of a burst error, large amounts of continuous data as well as redundant data may be lost, and correction may be difficult or impossible. To overcome this, data is often interleaved or dispersed through the data stream prior to storage or transmission. If a burst error occurs after the interleaving stage, it damages a continuous section of data. However, on playback, the bitstream is de interleaved; thus, the data is returned to its original sequence and conversely the errors are distributed through the bitstream. With valid data and valid redundancy now surrounding the damaged data, the algorithm is better able to reconstruct the damaged data. FIG. 16 shows an example of interleaving and de-interleaving, with a burst error occurring during storage or transmission. Following de-interleaving, the errors have been dispersed, facilitating error correction.
FIG. 16 Zero-, one-, two-, and three-word delays perform interleaving and
de-interleaving for error dispersion prior to correction.
Interleaving provides an important advantage. Without interleaving, the amount of redundancy would be dictated by the size of the largest correctable burst error. With interleaving, the largest error that can occur in any block is limited to the size of the interleaved sections. Thus, the amount of redundancy is determined not by burst size, but by the size of the interleaved section. Simple delay interleaving effectively disperses data. Many block checksums work properly if there is only one word error per block. A burst error exceeds this limitation; however, interleaved and de-interleaved data may yield only one erroneous word in a given block. Thus, interleaving greatly increases burst-error correctability of block codes. Bit interleaving accomplishes much the same purpose as block interleaving: it permits burst errors to be handled as shorter burst errors or random errors. Any interleaving process requires a buffer long enough to hold the distributed data during both interleaving and de interleaving.
Cross-Interleaving
Interleaving may not be adequate when burst errors are accompanied by random errors. Although the burst is scattered, the random errors add additional errors in a given word, perhaps overloading the correction algorithm.
One solution is to generate two correction codes, separated by an interleave and delay. When block codes are arranged in rows and columns two-dimensionally, the code is called a product code (or cross word code). The minimum distance is the product of the distances of each code. When two block codes are separated by both interleaving and delay, cross-interleaving results. In other words, a Cross-Interleave Code (CIC) comprises two (or more) block codes assembled with a convolutional structure, as shown in FIG. 17. The method is efficient because the syndromes from one code can be used to point to errors, which are corrected by the other code.
Because error location is known, correctability is enhanced. For example, a random error is corrected by the interleaved code, and a burst error is corrected after deinterleaving. When both codes are single-erasure correcting codes, the resulting code is known as a Cross Interleave Code. In the Compact Disc format, Reed- Solomon codes are used and the algorithm is known as the Cross-Interleave Reed-Solomon code (CIRC). Product codes are used in the DVD and Blu-ray formats.
An example of a simple CIC encoder is shown in Fig. 18. The delay units produce interleaving, and the modulo 2 adders generate single-erasure correcting codes. Two parity words (P and Q) are generated, and with two single erasure codes, errors are efficiently corrected. Triple-word errors can be corrected; however, four-word errors produce double-word errors in all four of the generated sequences, and correction is impossible. The CIC enjoys the high performance of a convolutional code but without error propagation, because any uncorrectable error in one sequence always becomes a one-word error in the next sequence and thus can be easily corrected.
FIG. 17 A cross-interleave code encoder. Syndromes from the first block are
used as error pointers in the second block. In the CD format, k2 = 24, n2 =
28, k1 = 28, and n1 = 32; the C1 and C2 codes are Reed-Solomon codes.
FIG. 18 An example of a CIC encoder and its output sequence.
Reed-Solomon Codes
Reed-Solomon codes were devised by Irving Reed and Gustave Solomon in 1960, at the Massachusetts Institute of Technology, Lincoln Laboratories. They are an example of an important subclass of codes known as q-ary BCH codes, devised by Raj Chandra Bose, Dwijendra Kumar Ray-Chaudhuri, and Alexis Hocquenghem in 1959 and 1960. BCH codes are a subclass of Hamming codes.
Reed-Solomon codes are cyclic codes that provide multiple-error correction. They provide maximum correcting efficiency. They define code symbols from n-bit bytes, with codewords consisting of 2n - 1 of the n-bit bytes. If the error pattern affects s bytes in a codeword, 2s bytes are required for error correction. Thus 2n - 1 - 2s bytes are available for data. When combined with cross-interleaving, Reed-Solomon codes are effective for audio applications because the architecture can correct both random and burst errors.
Reed-Solomon codes exclusively use polynomials derived using finite field mathematics known as Galois Fields (GF) to encode and decode block data. Galois Fields, named in honor of the extraordinary mathematical genius Evariste Galois (who devised them before his death in a duel at age 20), comprise a finite number of elements with special properties. Either multiplication or addition can be used to combine elements, and the result of adding or multiplying two elements is always a third element contained in the field. For example, when an element is raised to higher powers, the result is always another element in the field. Such fields generally only exist when the number of elements is a prime number or a power of a prime number. In addition, there exists at least one element called a primitive such that every other element can be expressed as a power of this element.
For error correction, Galois Fields yield a highly structured code, which ultimately simplifies implementation of the code. In Reed-Solomon codes, data is formed into symbols that are members of the Galois Field used by the code; Reed-Solomon codes are thus non-binary BCH codes. They achieve the greatest possible minimum distance for the specified input and output block lengths.
The minimum distance, the number of non-binary symbols in which the sequences differ, is given by: d = n - k + 1. The size of the Galois Field, which determines the number of symbols in the code, is based on the number of bits comprising a symbol; 8-bit symbols are commonly used.
The code thus contains 28 - 1 or 255 8-bit symbols. A primitive polynomial often used in GF(28) systems is x8 + x4 + x3 + x2 + 1.
Reed-Solomon codes use multiple polynomials with roots that locate multiple errors and provide syndromes to correct errors. For example, the code can use the input word to generate two parity polynomials, P and Q. The P parity can be a modulo 2 sum of the symbols. The Q parity multiplies each input word by a different power of the GF primitive element. If one symbol is erroneous, the P parity gives a nonzero syndrome S1. The Q parity yields a syndrome S2; its value is S1, raised to a power-the value depending on the position of the error. By checking this relationship between S1 and S2, the Reed-Solomon code can locate the error. When a placed symbol is in error, S2 would equal S1 multiplied by the element raised to the placed power. Correction is performed by adding S1 to the designated location. This correction is shown in the example below. Alternatively, if the position of two errors is already known through detection pointers, then two errors in the input can be corrected. For example, if the second and third symbols are flagged, then S1 is the modulo 2 sum of both errors, and S2 is the sum of the errors multiplied by the second and third powers.
To illustrate the operation of a Reed-Solomon code, consider a GF(23) code comprising 3-bit symbols. In this code, a is the primitive element and is the solution to the equation:
F(x) = x3 + x + 1 = 0 such that an irreducible polynomial can be written:
a3 + a + 1 = 0
... where + indicates modulo 2 addition. The elements can be represented as ordinary polynomials:
Because = x, using the properties of the Galois Field and modulo 2 (where 1 + 1 = + = 2 + 2 = 0) we can create a logarithmic representation of the irreducible polynomial elements in the field where the bit positions indicate polynomial positions:
In this way, all possible 3-bit symbols can be expressed as elements of the field (0, 1 = 7, , 2, 3, 4, 5, and 6) where is the primitive element (010). Elements can be multiplied by simply adding exponents, always resulting in another element in the Galois Field. For example:
The complete product table for this example GF(23) code is shown in FIG. 19; the modulo 7 results can be seen. For example, 4 6 = 10, or 3. Using the irreducible polynomials and the product table, the correction code can be constructed. Suppose that A, B, C, and D are data symbols and P and Q are parity symbols. The Reed- Solomon code will satisfy the following equations:
Using the devised product laws, we can solve these equations to yield:
FIG. 19 The product table for a GF(23) code with F(x) = x3 + x + 1 and primitive
element 010.
For example, given the irreducible polynomial table, if:
we can solve for P and Q using the product table:
Thus:
P = 101 = a6 Q = 110 = a4
Errors in received data can be corrected using syndromes, where a prime () indicates received data:
If each possible error pattern is expressed by Ei , we write the following:
If there is no error, then S1 = S2 = 0.
If symbol A is erroneous, S1 = EA and S2 = 6S1.
If symbol B is erroneous, S1 = EB and S2 = 5S1.
If symbol C is erroneous, S1 = EC and S2 = 4S1.
If symbol D is erroneous, S1 = ED and S2 = 3S1.
If symbol P is erroneous, S1 = EP and S2 = 2S1.
If symbol Q is erroneous, S1 = EQ and S2 = 1S1.
In other words, an error results in nonzero syndromes; the value of the erroneous symbols can be determined by the difference of the weighting between S1 and S2. The ratio of weighting for each word is different thus single-word error correction is possible. Double erasures can be corrected because there are two equations with two unknowns. For example, if this data is received:
We can calculate the syndromes (recalling that 1 + 1 = + = 2 + 2 = 0):
Because S2 = 4S1 (that is, 5 = 4 ·), symbol C must be erroneous and because S1 = EC = 010, C = C + EC = 001 + 010 = 011, thus correcting the error.
In practice, the polynomials used in CIRC are:
P + a6A + a1B + a2C + a5D + a3E Q + a2A + a3B + a6C + a4D + a1E and the syndromes are:
S1 = A' + B' + C' + D' + E' + P' + Q' S2 = a7A' + a6B' + a5C' + a4D' + a3E' + a2P' + a1Q'
Because Reed-Solomon codes are particularly effective in correcting burst errors, they are highly successful in digital audio applications when coupled with error-detection pointers such as CRCC and interleaving.
Reed-Solomon codes are used for error correction in applications such as CD, DVD, Blu-ray, direct broadcast satellite, digital radio, and digital television.
Cross-Interleave Reed-Solomon Code (CIRC)
The Cross-Interleave Reed-Solomon Code (CIRC) is a quadruple-erasure (double-error) correction code that is used in the Compact Disc format. CIRC applies Reed- Solomon codes sequentially with an interleaving process between C2 and C1 encoding. Encoding carries data through the C2 encoder, then the C1 encoder. Decoding reverses the process.
In CIRC, C2 is a (28,24) code, that is, the encoder inputs 24 symbols, 28 symbols (including four parity symbols) are output. C1 is a (32,28) code; the encoder inputs 28 symbols, and 32 symbols (with four additional parity symbols) are output. In both cases, because 8-bit bytes are used, the size of the Galois Field is GF(28); the calculation is based on the primitive polynomial: x8 + x4 + x3 + x2 + 1.
Minimum distance is 5. Up to four symbols can be corrected if the error location is known, and two symbols can be corrected if the location is not known.
Using a combination of interleaving and parity to make the data more robust against errors encountered during storage on a CD, the data is encoded before being placed on the disc, and then decoded upon playback. The CIRC encoding algorithm is shown in FIG. 20; the similarity to the general structure shown in FIG. 17 is evident. Using this encoding algorithm, symbols from the audio signal are cross-interleaved, and Reed-Solomon encoding stages generate P and Q parity symbols.
The CIRC encoder accepts twenty-four 8-bit symbols, that is, 12 symbols (six 16-bit samples) from the left channel and 12 from the right channel. Interestingly, the value of 12 was selected by the designers because it has common multiples of 2, 3, and 4; this would have allowed the CD to more easily also offer 3- or 4-channel implementations-a potential that never came to fruition.
An interleaving stage assists interpolation. A two-symbol delay is placed between even and odd samples. Because even samples are delayed by two blocks, interpolation is possible where two uncorrectable blocks occur. The symbols are scrambled to separate even- and odd numbered symbols; this process assists concealment. The 24-byte parallel word is input to the C2 encoder that produces four symbols of Q parity. Q parity is designed to correct one erroneous symbol, or up to four erasures in one word. By placing the parity symbols in the center of the block, the odd/even distance is increased. This permits interpolation over the largest possible burst error.
FIG. 20 The CIRC encoding algorithm.
In the cross-interleaving stage, 28 symbols are delayed by differing periods. These periods are integer multiples of four blocks. This convolutional interleave stores one C2 word in 28 different blocks, stored over a distance of 109 blocks. In this way, the data array is crossed in two directions. Because the delays are long and of unequal duration, correction of burst errors is facilitated. Twenty eight symbols (from 28 different C2 words) are input to the C1 encoder, producing four P parity symbols. P parity is designed to correct single-symbol errors and detect and flag double and triple errors for Q correction.
An interleave stage delays alternate symbols by one symbol. This odd/even delay spreads the output symbols over two data blocks. In this way, random errors cannot corrupt more than one symbol in one word even if there are two erroneous adjacent symbols in one block. The P and Q parity symbols are inverted to provide nonzero P and Q symbols with zero data. Thirty-two 8-bit symbols leave the CIRC encoder.
The error processing must be decoded each time the disc is played to de-interleave the data, and perform error detection and correction. When a Reed-Solomon decoder receives a data block (consisting of the original data symbols plus the parity symbols) it uses the received data to recalculate the parity symbols. If the recalculated parity symbols match the received parity symbols, the block is assumed to be error-free. If they differ, the difference syndromes are used to locate the error. Erroneous words are flagged, for example, as being correctable, uncorrectable, or possibly correctable. Analysis of the flags determines whether the errors are to be corrected by the correction code, or passed on for interpolation. The CIRC decoding algorithm is shown in FIG. 21.
FIG. 21 The CIRC decoding algorithm.
A frame of thirty-two 8-bit symbols is input to the CIRC decoder: twenty-four are audio symbols and eight are parity symbols. Odd-numbered symbols are passed through a one-symbol delay. In this way, even-numbered symbols in a frame are de-interleaved with the odd-numbered symbols in the next frame. Audio symbols are restored to their original order and disc errors are scattered. This benefits C1 correction, especially for small errors in adjoining symbols. Following this de-interleaving, parity symbols are inverted.
Using four P parity symbols, the C1 decoder corrects random errors and detects burst errors. The C1 decoder can correct one erroneous symbol in each frame. If there is more than one erroneous symbol, the 28 data symbols are marked with an erasure flag and passed to the C2 decoder. Valid symbols are passed along unprocessed.
Convolutional de-interleaving between the decoders enables the C2 decoder to correct long burst errors. The frame input to C2 contains symbols from C1 decoded at different times; thus, symbols marked with an erasure flag are scattered. This assists the C2 decoder in correcting burst errors. Symbols without a flag are assumed to be error-free, and are passed through unprocessed.
Given pre-corrected data, and help from de-interleaving, C2 can correct burst errors as well as random errors that C1 was unable to correct. Using four Q parity symbols, C2 can detect and correct single-symbol errors and correct up to four symbols, as well as any symbols mis-corrected by C1 decoding. C2 also can correct errors that might occur in the encoding process itself, rather than on the disc. When C2 cannot accomplish correction, for example, when more than four symbols are flagged, the 24 data symbols are flagged and passed on for interpolation. Final descrambling and delay completes CIRC decoding.
CIRC Performance Criteria
The integrity of data stored on a CD and passing through a CIRC algorithm can be assessed through a number of error counts. Using a two-digit nomenclature, the first digit specifies the number of erroneous symbols (bytes), and the second digit specifies at which decoder (C1 or C2) they occurred. Three error counts (E11, E21, and E31) are measured at the output of the C1 decoder. The E11 count specifies the frequency of occurrence of single-symbol (correctable) errors per second in the C1 decoder. E21 indicates the frequency of occurrence of double-symbol (correctable) errors in the C1 decoder. E31 indicates the frequency of triple-symbol (uncorrectable at C1) errors in the C1 decoder. E11 and E21 errors are corrected in the C1 stage. E31 errors are uncorrected in the C1 stage, and are passed along to the second C2 stage of correction.
There are three error counts (E12, E22, and E32) at the C2 decoder. The E12 count indicates the frequency of occurrence of a single-symbol (correctable) error in the C2 decoder measured in counts per second. A high E12 count is not problematic because one E31 error can generate up to 30 E12 errors due to interleaving. The E22 count indicates the frequency of two-symbol (correctable) errors in the C2 decoder. E22 errors are the worst correctable errors; the E22 count indicates that the system is close to producing an uncorrectable error; a CD-ROM with 15 E22 errors would be unacceptable even though the errors are correctable. A high E22 count can indicate localized damage to the disc, from manufacturing defect or usage damage. The E32 count indicates three or more symbol (uncorrectable) errors in the C2 decoder, or unreadable data in general; ideally, an E32 count should never occur on a disc. E32 errors are sometimes classified as noise interpolation (NI ) errors; when an E32 error occurs, interpolation must be performed. If a disc has no E32 errors, all data is output accurately.
The block-error rate (BLER) measures the number of frames of data that have at least one occurrence of uncorrected symbols (bytes) at the C1 error-correction decoder input (E11 + E21 + E31); it is thus a measure of both correctable and uncorrectable errors at that decoding stage. Errors that are uncorrectable at this stage are passed along to the next error-correction stage. BLER is a good general measure of disc data quality. BLER is specified as rate of errors per second. The CD standard sets a maximum of 220 BLER errors per second averaged over 10 seconds for audio discs; however, a well manufactured disc will have an average BLER of less than 10. A high BLER count often indicates poor pit geometry that disrupts the pickup's ability to read data, resulting in many random-bit errors. A high BLER might limit a disc's lifetime as other scratches accumulate to increase total error count. Likewise a high BLER may cause playback to fail in some players. The CD block rate is 7350 blocks per second; hence, the maximum BLER value of 220 counts per second shows that 3% of frames contain a defect. This defines the acceptable (correctable) error limit; greater frequency might lead to audible faults. The BLER does not provide information on individual defects between 100 and 300 µm, because the BLER responds to defects that are the size of one pit. BLER is often quoted as a 1-second actual value or as a sliding 10-second average across the disc, as well as the maximum BLER encountered during a single 10-second interval during the test.
The E21 and E22 signals can be combined to form a burst-error (BST) count. It counts the number of consecutive C2 block errors exceeding a specified threshold number. It generally indicates a large physical defect on the disc such as a scratch, affecting more than one block of data. For example, if there are 14 consecutive block errors and the threshold is set at seven blocks, two BST errors would be indicated. This count is often tabulated as a total number over an entire disc. A good quality control specification would not allow any burst errors (seven frames) to occur. In practice, a factory-fresh disc might yield BLER = 5, E11 = 5, E21 = 0, and E31 = 0. E32 uncorrectable errors should never occur in a new disc. FIG. 22 shows an example of the error counts measured from a Compact Disc with good-quality data readout. Error counts are measured vertically, across the duration of this 50-minute disc. As noted above, the high E12 error count is not problematic.
Following CIRC error correction, this disc does not have any errors in its output data.
The success of CIRC error correction ultimately depends on the implementation of the algorithm. Generally, CIRC might provide correction of up to 3874 bits, corresponding to a track-length defect of 2.5 mm. Good concealment can extend to 13,282 bits, corresponding to an 8.7-mm defect, and marginal concealment can extend to approximately 15,500 bits.
Product Codes
The CIRC is an example of a cross-interleaved code in which two codes are separated by convolutional interleaving. In two-dimensional product codes, two codes are serially separated by block interleaving. The code that is the first to encode and the last to decode is called the outer C2 code. The code that is the second to encode and the first to decode is called the inner C1 code. Product codes thus use the method of crossing two error-correction codes. If C2 is a (n2, k2) block code and C1 is a (n1, k1) block code, then they yield a (n1n2, k1k2) product code with k1k2 symbols in an array. The C2 code adds P parity to the block rows, and the C1 code adds Q parity to the block columns as shown in FIG. 23. Every column is a codeword of C1. When linear block codes are used, the bottom row words are also codewords of C2. The check data in the lower right-hand corner (intersection of the P column and the Q row) is a check on the check data and can be derived from either column or row check data.
FIG. 22 Example of error counts across a 50-minute Compact Disc. A. E11 error
count. B. E21 error count. C. E31 error count. D. BLER error count. E. E12
error count. F. E22 error count. G. E32 error count (no errors).
FIG. 23 Block diagram of a product code showing outer-row (P) redundancy
and inner-column (Q) redundancy. A burst error is flagged in the C1 decoder
and corrected in the C2 decoder.
During decoding, Q parity is used by the C1 decoder to correct random-bit errors, and burst errors are flagged and passed through de-interleaving to the C2 decoder.
Symbols are passed through de-interleaving so that burst errors in inner codewords will appear as single-symbol errors in different codewords. The P parity and flags are used by the C2 decoder to correct errors in the inner codewords.
Product codes are used in many audio applications. For example, the DAT format provides an example of a product code in which data is encoded with Reed-Solomon error correction code over a Galois Field GF(28) using the polynomial x8 + x4 + x3 + x2 + 1. The inner code C1 is a (32,28) Reed-Solomon code with a minimum distance of 5. Four bytes of redundancy are added to the 28 data bytes. The outer code C2 is a (32,26) Reed-Solomon code with a minimum distance of 7. Six bytes of redundancy are added to the 26 data bytes. Both C1 and C2 codes are composed of 32 symbols and are orthogonal with each other. C1 is interleaved over two blocks, and C1 is interleaved across an entire PCM data track, every four blocks. As with the Compact Disc, the error-correction code used in DAT endeavors to detect and correct random errors (using the inner code) and eliminate them prior to de-interleaving; burst errors are detected and flagged.
Following de-interleaving, burst errors are scattered and more easily corrected. Using the error flags, the outer code can correct remaining errors. Uncorrected errors must be concealed.
Two blocks of data are assembled in a frame, one from each head, and placed in a memory arranged as 128 columns by 32 bytes. Samples are split into two bytes to form 8-bit symbols. Symbols are placed in memory, reserving a 24-byte wide area in the middle columns. Rows of data are applied to the first (outer C2 code) Reed- Solomon encoder, selecting every fourth column, finishing at column 124 and so yielding 26 bytes. The Reed- Solomon encoder generates six bytes of parity yielding 32 bytes. These are placed in the middle columns, at every fourth location (52, 56, 60, and so on). The encoder repeats its operation with the second column, taking every fourth byte, finishing at column 125. Six parity bytes are generated and placed in every fourth column (53, 57, 61, and so on). Similarly, the memory is filled with 112 outer codewords. (The final eight rows require only two passes because odd-numbered columns have bytes only to row 23.) Memory is next read by columns. Sixteen even numbered bytes from the first column, and the first 12 even numbered bytes from the second column are applied to the second (inner C1 code) encoder, yielding four parity bytes for a total codeword of 32 bytes. This word forms one recorded synchronization block. A second pass reads the odd-numbered row samples from the first two columns of memory, again yielding four parity bytes and another synchronization block. Similarly, the process repeats until 128 blocks have been recorded.
The decoding procedure utilizes first the C1 code, then the C2 code. In C1 decoding, a syndrome is calculated to identify data errors as erroneous symbols. The number of errors in the C1 code is determined using the syndrome; in addition, the position of the errors can be determined.
Depending on the number of errors, C1 either corrects the errors or flags the erroneous symbols. In C2 decoding, a syndrome is again calculated, the number and position of errors determined, and the correction is carried out. During C1 decoding, error correction is performed on one or two erroneous bytes due to random errors. For more than two errors, erasure correction is performed using C1 flags attached to all bytes in the block prior to de-interleaving.
After de-interleaving, these errors are distributed and appear as single-byte errors with flags. The probability of uncorrectable or misdetected errors increases along with the number of errors in C1 decoding. It is negligible for a single error because all four syndromes will agree on the error. A double error increases the probability.
The C2 decoding procedure is selected to reduce the probability of misdetection. For example, the optimal combination of error correction and erasure correction can be selected on the basis of error conditions. In addition, C2 carries out syndrome computation even when no error flags are received from C1. Because C1 has corrected random errors, C2's burst-error correction is not compromised. C2 independently corrects one-or two-byte errors in the outer codeword. For two to six erroneous bytes in the outer codeword, C2 uses flags supplied by C1 for erasure correcting. Because the outer code undergoes four-way interleaving, four erroneous synchronization blocks result in only one erroneous byte in an outer codeword. Because C2 can correct up to six erroneous bytes, burst errors up to 24 synchronization blocks in duration can thus be corrected.
Product codes can outperform other codes in modern audio applications; they demand more memory for implementation, but in many applications this is not a serious detriment. Product codes provide good error correction performance in the presence of simultaneous burst and random errors and are widely used in high density optical recording media such as DVD and Blu-ray discs. DVD is discussed in Section 8 and Blu-ray is discussed in Section 9.
Error Concealment
As noted, a theoretically perfect error-detection and error correction method could be devised in which all errors are completely supplanted with redundant data or calculated with complete accuracy. However, such a scheme would be impractical because of the data overhead. A practical error-correction method balances those limitations against the probability of uncorrected errors and allows severe errors to remain uncorrected. However, subsequent processing-an error-concealment system-compensates for those errors and ensures that they are not audible.
Several error-concealment techniques, such as interpolation and muting, have been devised to accomplish this.
Generally, there are two kinds of uncorrectable errors output from correction algorithms. Some errors can be properly detected; however, the algorithm is unable to correct them. Other errors are not detected at all or are mis-corrected. The first type of error, detected but not corrected, can usually be concealed with properly designed concealment methods. However, undetected and mis-corrected errors often cannot be concealed and may result in an audible click in the audio output. These types of errors, often caused by simultaneous random and burst errors, must be minimized. Thus, an error-correction system aims to reduce undetected errors in the error-correction algorithm, and then relies on the error concealment methods to resolve detected but not corrected errors.
Interpolation
Following de-interleaving, most errors, even burst errors, are interspersed with valid data words. It is thus reasonable to use techniques in which surrounding valid data is used to calculate new data to replace the missing or uncorrected data. This technique works well, provided that errors are sufficiently dispersed and there is some correlation between data values. Fortunately, digital data comprising a musical selection can often undergo interpolation without adverse audibility. Although it is non-intuitive, studies have shown that within limits, the time duration of an error does not overly affect perception of the error.
In its simplest form, interpolation holds the previous sample value and repeats it to cover the missing or incorrect sample. This is called zero-order or previous value interpolation. In first-order interpolation, sometimes called linear-order interpolation, the erroneous sample is replaced with a new sample derived from the mean value of the previous and subsequent samples. In many digital audio systems, a combination of zero- and first-order interpolation is used. If consecutive sample errors occur in spite of interleaving, then previous-value interpolation is used to replace consecutive errors, but the final held sample's value is calculated from the mean value of the held and subsequent sample. If the errors are random, that is, valid samples surround the errors, then mean value calculations are used. One interpolation strategy is shown in FIG. 24. Other higher-order interpolation is sometimes used; nth-order interpolation uses a higher-order polynomial to calculate substituted data. In practice, third and fifth-order interpolations are sometimes used. Clearly, any interpolation calculations must be accomplished quickly enough to maintain the data rate. The results of one experiment in relative values of interpolation noise are shown in FIG. 25.
FIG. 24 Interpolation is used to conceal errors. For example, a previous
value can be held, followed by a calculation of the mean value.
FIG. 25 Noise characteristics for different interpolation methods (for 100-bit
burst length, pure tone signals, and uncorrectable errors).
Muting
Muting is the simple process of setting the value of missing or uncorrected words to zero. This silence is preferable to the unpredictable sounds that can result from decoding incorrect data. Muting might be used in the case of uncorrected errors, which would otherwise cause an audible click at the output. The momentary interruption from a brief mute might be imperceptible, but a click would typically be audible. Also, in the case of severe data damage or player malfunction, it is preferable to mute the data output. To minimize audibility of a mute, muting algorithms gradually attenuate the output signal's amplitude prior to a mute, and then gradually restore the amplitude afterward. For example, gain can be adjusted by multiplying successive samples by attenuation coefficients over a few milliseconds. Of course, gain reduction must begin prior to the error itself, to allow time for a smooth fade. This is easily accomplished by delaying all audio samples briefly and feeding the mute flag forward. Very short-duration muting cannot be perceived by the human ear.
Concealment strategies are assisted when audio channels are processed independently, for example, by muting only one channel rather than both.
Duplication
One of the benefits of digital audio recording is the opportunity to copy recordings without the inevitable degradation of analog duplication. Although digital audio duplication can be lossless, its success depends on the success of error correction. Although error-correction methods provide completely correct data, error concealment does not. Under marginal circumstances, error-concealment techniques do introduce audible errors into copied data. Thus, subsequent generations of digital copies could contain an accumulation of concealed errors not present in the original. As a result, errors must be corrected at their origin. Routine precautions of clean media, clean machine mechanisms, and proper low-jitter interfacing are important for digital audio duplication, particularly when many generations of copying are anticipated. In practice, digital audio data can be copied with high reliability. When a file is copied and contains exactly the same values as the original file, it is a clone of the original, with an implicit sampling frequency. Neither the original nor the cloned values have control over the storage media or playback conditions. The copy will sound the same as the original, but only if its playback conditions equal those of the original file's playback conditions. A simple way to test bit-for-bit accuracy is to load both files into a workstation and exactly synchronize the files to sample accuracy, invert one file and add them. A null result shows bit-for-bit accuracy. Likewise, a residue signal shows the difference between the files.