|
IBM Japan's Tokyo Research Laboratory Develops a Parallel Processing Algorithm for Reed-Solomon Error-Correcting Codes,
Making Data Error Correction over 10 Times Faster
IBM Japan, Ltd. announced the following news on October 6. This is the English translation of the Japanese release statement.
TOKYO, October 6, 1999
IBM Japan, Ltd. (president: Kakutaro Kitashiro), on October 6 announced that its Tokyo Research Laboratory (Yamato City, Kanagawa Prefecture) had developed a new hardware algorithm that allows parallel processing of Reed-Solomon error-correcting codes (*1) at a speed more than 10 times higher than previously possible.
With the spread of the Internet and e-business, the amount of data processed by computers is increasing at an accelerated pace. The reliability of data processing must also improve proportionally just in order to maintain today's system-level reliability. This reliability is provided by special "error-correcting codes" that use advanced mathematics to automatically detect and correct errors. The two most common types of error-correcting codes are called Hamming codes and Reed-Solomon codes.
Hamming codes can correct an error found in a single bit, and can detect -- but not correct -- an error affecting two bits. Thanks to their simple error correction processes, Hamming codes can be decoded in parallel, which allows very fast error correction at speeds much greater than 1 Gb/s (a billion bits per second).
In contrast, Reed-Solomon codes can correct an error affecting a sequence of bits (called a "symbol")(*2). Although they allow highly advanced error corrections, decoding them often requires complex arithmetic operations, making them unsuited to parallel processing. For example, pipeline processing (*3) of 8-bit data at 100 MHz allows a processing speed of only 800 Mb/s (800 million bits per second).
For this reason, Reed-Solomon codes have so far been used mainly in areas where relatively low-speed data processing is acceptable, such as communication applications, and in secondary storage devices such as hard disks and CD-ROMs. They have not been widely adopted in areas where rapid processing is required.
This situation is about to change. The new IBM algorithm opens up a whole new range of applications for Reed-Solomon error correction by speeding it up to a level comparable with that of Hamming code error correction.
To achieve this, IBM Japan's Tokyo Research Laboratory applied the mathematical formulations of symmetric functions used in today's quantum mechanics (*5) to the decoding of Reed-Solomon codes. This resulted in both faster processing, and fewer arithmetic circuits required in parallel processing.
The resulting improvement in processing speed has been clearly demonstrated. For example, when the new algorithm was used in a random 4-byte error correction circuit designed and fabricated by using standard 0.35-um ASIC technology, the algorithm provided parallel processing of a 320-bit-long sequence of data in 45 nanoseconds (45 billionths of a second). This is equivalent to a processing speed of over 7 Gb/s (7 billion bits a second)--almost 10 times faster than what is expected from the sequential decoding algorithm. When used with more advanced ASIC technology of 0.25um or less, and with pipeline processing, the algorithm is expected to provide a processing speed that is up to 10 times faster still.
The sizes of circuits have also been further reduced, thanks to the use of a new circuit optimization algorithm and circuit-sharing methodology for massive combinational circuits. The new circuit, which has about 30,000 gates, is comparable in size with a Hamming code parallel processing circuit. Thus, it could be embedded as a macro in a single chip containing other circuits, such as a CPU and/or a memory controller.
In addition to processing at a very high speed, this highly advanced error correction circuit, which consists of only combinational circuits (i.e., not clock circuits or registers) can maintain power consumption at an acceptable level. Thus, it can be applied to memory systems with the aim of effecting considerable savings in the refresh power consumption of DRAMs used in mobile and pervasive devices.
As larger amounts of data are processed at higher speeds in the future, the demand for advanced, high-speed error correcting codes should increase. IBM Japan's Tokyo Research Laboratory is planning to continue exploring this field and to develop the basic technologies needed for more reliable systems in the coming generation of information processing devices.
The results of TRL's current research on error correcting-codes are expected to be presented at ICCD '99 (the 1999 IEEE International Conference on Computer Design), to be held in Austin, Texas, on October 11-13, 1999, and DFT '99 (the 1999 IEEE International Symposium on Defect and Fault Tolerance in VLSI systems), to be held in Albuquerque, New Mexico, on November 1-3, 1999.
Terminology:
*1 Reed-Solomon error-correcting codes
These error-correcting codes were announced in 1960 in a paper by Irving S. Reed and Gustave Solomon.
*2 Correct an error affecting a sequence of bits (called a "symbol")
Designed to correct an error in a sequence of bits (a "symbol"), Reed-Solomon error-correcting codes can correct an error in up to eight consecutive bits with single-symbol correction capability, provided a symbol consists of eight bits. With two-symbol correction capability, the codes can correct an error in up to 16 consecutive bits or in two sequences of eight consecutive bits.
*3 Pipeline processing
This is a processing technique used to increase the overall speed of processing. Here, the whole processing operation is treated like an assembly line operation, and is broken down into several stages. These are then assigned to corresponding processing mechanisms, which process the assigned stages concurrently. This methodology is now used broadly to improve the processing speed of CPUs.
*4 New algorithm
Unlike an iterative algorithm, which is normally implemented by means of sequential circuits, this new algorithm decodes Reed-Solomon codes in parallel, using combinational circuits alone. An iterative algorithm solves a problem by repeatedly using the arithmetic circuits and the registers that store the intermediate information, with an additional control circuit. In contrast, a parallel-processing algorithm that uses combinational circuits does the processing all at once in parallel by arranging the arithmetic circuits alone in a way that suits such processing. Generally, when carrying out the same processing, the former algorithm can work with a smaller number of circuits, but takes longer to complete. The latter, though it requires a larger number of circuits, finishes the processing much faster.
*5 Quantum mechanics
This is a field of physics that provides a basis for describing the behavior of microscopic particles such as electrons. In the research described in this release, IBM Japan's Tokyo Research Laboratory used a theoretical framework involving the fractional quantum Hall effect.
|
