This article refers to the address: http://
Abstract: This paper introduces the design method of CD-ROM format data soft decoding module applied to embedded system; analyzes the data structure of CD-ROM format, gives the software implementation method of EDC and ECC decoding algorithm and the software flow chart of the module.Keywords: CD-ROM format soft decoding EDC error detection ECC error correction
introduction
CD-ROM is a large-capacity, low-cost storage device that is widely used at present. In order to reduce the bit error rate, the original data is formatted and channel encoded, and then written into the CD-ROM disc; when reading, it needs to be decoded by channel and formatted to obtain the required original data. . The process of reading and writing CD-ROM data is shown in Figure 1.
In general audio-visual equipment (such as VCD machines) and personal computers, the decoding process of CD-ROM data is performed by a dedicated decoding chip; while CD-ROM can be applied not only to audio-visual equipment and personal computers, but also to An embedded system that needs to read large amounts of data. For example, in a vehicle-like system, a CD-ROM can be used to store geographic information data. The decoding method of CD-ROM data in the embedded system is flexible, and a dedicated decoding chip (temporarily called hard decoding) can be used, or can be completed by a decoding program of the processor (soft decoding). Soft decoding has its unique advantages over hard decoding. Because it only needs to add a decoding program module, it saves the dedicated decoding chip circuit, simplifies the hardware circuit of the system and reduces the cost of the system. As shown in FIG. 1, after the CD-ROM data is decoded by the channel, the CD-ROM format data organized in a sector structure is obtained, and CD-ROM format decoding is also required to obtain the final user data. This paper introduces the design of CD-ROM format data soft decoding module in embedded system.
1 sector structure of CD-ROM format data
The CD-ROM data is encoded by the sector as a basic unit. The sectors obtained after the channel decoding process have different structures for different data sources. For CD-DA (two-channel CD audio) data, since there is no formatted encoding, user data can be directly obtained; while CD-ROM data and VCD data are formatted and encoded into a sector structure by CD-ROM, CD-ROM format decoding can get user data.
There are two modes for CD-ROM sectors: Mode 1 and Mode 2. Its sector structure is shown in Figure 2.
As can be seen from Fig. 2, the CD-ROM format data of one sector has a total of 2352 bytes. Among them, the two sector modes have 12 bytes of synchronization information and 4 bytes of time information (header information). If it is mode 1, there are 4 bytes of loop redundancy error code, 8 bytes of null bytes, 276 bytes of error correction code, including 172 bytes of P check word and 104 bytes of Q check Word, user data is only 2048 bytes. In the case of mode 2, except for the synchronization information and the header information, the remaining 2336 bytes are all user data.
   In practice, the data read from the disc may not be completely correct due to the performance of the disc's materials, the limitations of the disc manufacturing technology, the performance of the drive, and improper use. According to statistics, an unused read-only disc has an original bit error rate of about 3 × 10 -4 , a disc with a fingerprint of about 6 × 10 -4 , and a disc with a scar of about 5 × 10 -3 . In response to this situation, the optical disc storage system uses powerful error detection and corrective measures: CIRC, EDC, ECC. After the data is decoded by the channel, the error rate is reduced from 10 -4 to 10 -5 to 10 -9 or less due to the CIRC error correction processing. For audio and image data, such a bit error rate is sufficient. However, to use computer file data, the bit error rate must be 10-12 or less, so a second error correction process must be used. This requirement can be achieved by EDC and ECC verification.
Therefore, mode 1 is mainly used to store data that is very sensitive to errors, such as computer program code; while mode 2 is mainly used to store data that is not sensitive to errors, such as images, audio, and the like.
On the basis of mode 2, the CD-ROM/XA format is further divided into two forms (FORM): Form 1 and Form 2. Its sector structure is shown in Figure 3. Our commonly used VCD is in the form 2 format of CD-ROM/XA.
It can be seen from the above that in addition to the sector mode 2, 2336 bytes of user data can be directly obtained, and the CD-ROM format decoding must also perform EDC error detection and ECC error correction processing. The principles and decoding algorithms of EDC error detection and ECC error correction are introduced below.
2 EDC error detection principle and algorithm in CD-ROM sector
The CD-ROM sector uses a 32-bit CRC (Cyclic Redundancy Check Code) error detection code, and its generator polynomial is
P(X)=(X 16+X 15+X 2+1)×(X 16+X 2+X+1)
The corresponding codeword is 0x18001801B. The data block used to calculate the CRC code is the data byte from the beginning of the sector to the end of the user data area. The long polynomial corresponding to the data of 2064 bytes of bytes 0 to 2063 is divided by P(X) to obtain a 32-bit remainder, which is placed at 2064 to 2067 bytes. The polynomial corresponding to the 2068 bytes of data can be divisible by the generator polynomial P(X). If it is not divisible, it indicates that the data is wrong. Therefore, our decoding process divises the generator polynomial by a polynomial of 2068 bytes of data. If the remainder is 0, the data is correct, otherwise the data is wrong.
But we can't directly perform long division, because it is impossible for a computer to directly use a very long binary number of 2068 × 8 bits for long division. According to the law of long division, operations are performed in units of bytes (8 bits), and each division divides the resulting remainder of the previous byte with this byte into a new number for division. The division is 33 bits, so the division of each byte must shift the number of this byte to the left by 24 bits, and combine with the last remainder to form a 32-bit binary number to divide the division. The main realization of modern code is as follows:
For(i=0;i<2068;i++)
Crc=edc_crc_32(crc,data_in[i],M32);
Where crc is the remainder and M32 is the binary number corresponding to the generator polynomial. The implementation code of the function edc_crc_32(int crc, int ch, int mask) is
Char edc_crc_32(int crc, int int mask){
Ch<<24;
For(int i=0;i<8;i++){
If(crc^ch)&0x80000000)
Crc=(crc<<1)^mask;
Else
Crc<<=1;
Ch<<=1;
}
Return crc;
}
It can be seen from the above code that the remainder of each byte is subjected to 8 shifts and 8 XOR operations. For data with the same ch value, this operation is completely repeated; for a large amount of CD-ROM data. Said that it is a great waste of resources. Therefore, in order to improve efficiency, the remainder of the 256 8-bit binary numbers can be made into a table, and the table is read into the memory before the program is run. By looking up the table, the efficiency of the code will be greatly improved. code show as below:
For(int i=0;i<2068;i++){
Temp=data_in[i]^(crc>>24));
Crc=(crc<<8)^crctable[temp];
}
In this way, in addition to the data table needs to occupy memory, the computational efficiency can theoretically increase by 8 bits. In fact, it uses a small amount of memory space in exchange for a great increase in efficiency. This is very useful in embedded systems.
3 ECC error correction principle and algorithm in CD-ROM sector
The ECC code in the CD-ROM sector, according to the ISO/IEC 10149 specification, uses the RSPC code on the GF (2 8) field to generate a 172-byte P-check match and a 104-byte Q check symbol. Primitive polynomial
P(x)=x 8+x 4+x 3+x 2+1
Original element
α=(0 0 0 0 0 0 1 0)
Construct 256 elements in GF(28).
The method of generating the P checksum Q check word is as shown in FIG. In each sector, bytes 12 to 2075 and bytes 2076 to 2351 in the ECC field have a total of 2340 bytes, which constitutes 1170 words. Each word S consists of two bytes B, the most significant bit byte MSB and the least significant bit byte LSB, respectively. The nth word consists of one-sided bytes:
S(n)=MSB[B(2n+13)]+LSB[B(2n+12)]
Where n=0, 1, 2, ..., 1169.
A block of 2064 bytes from byte 12 to 2075 is arranged into a 24×43 matrix, which can be regarded as a 24×43 matrix composed of one MSB byte and a 24×43 matrix composed of one LSB byte. .
The P check symbol is generated using the (26, 24) RS code. The 24 bytes of data of each column of 43 columns plus the 2 bytes of P check bytes on the columns corresponding to 24 rows and 25 rows constitute the column vector Vp. This constitutes a 26×43 matrix and satisfies the equation
After adding the P-check, a 26×43 matrix is ​​obtained, and the diagonal elements of the matrix are rearranged to obtain a new 26×43 matrix. Each row of the new matrix generates two Q-checks with the (45, 43) RS code. The byte is placed at the end. Set to VQ vector, satisfy the following equation
HQ×VQ=0
Where the check matrix is
The RS code error correction process is divided into three steps: 1 to calculate the syndrome; 2 to calculate the error position; 3 to calculate the error value.
The traditional ECC algorithm has an iterative algorithm and a large number of logic decoding algorithms, involving complex matrix operations and more mathematical knowledge, and the program implementation is also very complicated. Specific to our actual situation, we found that whether it is (26, 24) RS or (45, 43) RS, there are only two bytes of check digits, which can be solved by directly solving the binary equations. A simpler algorithm.
Let the check digits be Q1 and Q2, and the syndrome is calculated as follows (take the (26, 24) RS code as an example):
If it is found that S0 and S1 are not all 0, it can be concluded that the data has an error. If there is only one error, set the error value to mx and the error bit to ax. You can find the error position and error value by solving the following equations.
Note: The addition, subtraction, multiplication, and division operations in the equation solving process are all performed on the GF(2 8) domain. These operations must be specifically defined during programming.
If the calculated S0 = 0, S1 ≠0, then basically at least two errors can be concluded. In the case of multiple errors, error correction in individual in-row and column is powerless, but considering the array as a whole, some multiple errors can still be corrected. Reference Technology offers an algorithm called Layered ECC that eliminates multiple errors. The core idea is to alternate row and column error correction. Because multiple errors in the same row may be an error in the column from the perspective of the column, you can first correct the column, and then from the perspective of the row, you can become a single error, which can be corrected.
Both the (26, 24) RS code and the (45, 43) RS code can correct an error in any row and any column, and can reliably detect errors in rows and columns. The probability of an error in practice is much greater than the probability of multiple errors. Therefore, the error detection capability of EDC code words is very powerful.
4 CD-ROM format decoding program flow chart
The main program flow of this data processing module is shown in Figure 5. By detecting the synchronization word, a complete frame data is obtained from the data stream, and then the sector mode is obtained through the header information of the 16th byte of the sector, and then different processing is performed according to the mode. If it is mode 2, it can directly get 2336 bytes of user data, if necessary, CD-ROM/XA format processing: if sector mode 1, EDC error detection processing is required, if there is no error, 2048 bytes can be taken out. User data; if there is an error, perform ECC error correction processing: if the error correction is successful, directly extract 2048 bytes of user data. If there are too many errors and you can't correct them, an error message is reported.
For the CD-ROM/XA format, the corresponding processing can be performed according to the base sub-mode (ie, the mode 2). For Form 2, EDC error detection is performed, and 2324 bytes of user data can be obtained; and for Form 1, processing similar to Mode 1 can be performed, that is, after EDC error detection and ECC error correction, 2048 bytes of user data are obtained. .
When the program module is applied to a specific application system, it will appear in the form of a system subroutine.
Conclusion
In embedded systems, the implementation of data decoding should be flexible based on the characteristics and requirements of the specific application. This paper introduces the implementation method of CD-ROM format decoding by software, which is of good application value to the embedded system using CD-ROM.
GPS Personal Tracker Co., Ltd. , http://www.szgpstracker.com