Description:
A technique for verifying the integrity of binary data streams.
At a Glance
- New “low complexity” error detection method for analysis of transmitted digital data.
- Utilizes fewer computing resources and offers greater scalability over conventional Viterbi-based methods with no loss in detection performance.
- Superior to Viterbi for advanced encoding schemes incorporating both convolutional and block-based codes (Turbo Code, LDPC).
- Enables optimality examination of data – a feature not offered by other analysis methods.
- Application in cellular transmission, satellite communication, retrieval of stored data, bioinformatics, speech-to-text conversion, and any other process utilizing streaming of digital data.
Detailed Description
Fast, accurate transmission of digital information is a vital part of an increasing number of high-tech operations, such as reading of hard disk drives, cellular transmission, satellite communication and streaming video. Since channel noise may introduce errors, techniques have been devised to detect errors and enable reconstruction of the original data. The celebrated Viterbi algorithm has been widely implemented to detect errors in bitstreams encoded using forward error correction. However, the Viterbi algorithm scales exponentially in the memory of the sequence transmission system, making it a high complexity, very resource-consuming “maximum likelihood” error detection method that is ultimately limited in its application.
Research in the Electrical and Computer Engineering Department at Colorado State University has led to the development of a low complexity “maximum likelihood” error detection (LC-MLED) algorithm that offers superior performance and scalability to other methods. As industry transitions to suboptimal detection methods and increasingly sophisticated transmission systems (high data rate, advanced coding, multiple antennas), a low complexity method is becoming essential. The LC-MLED scales better with regards to key communication parameters, offers faster but guaranteed optimal detection performance and has lower power consumption (vital for mobile applications). The LC-MLED algorithm is also superior to Viterbi when advanced encoding schemes are used that incorporate both convolutional codes and block-based codes such as Turbo Code or LDPC code.
An added advantage of the LC-MLED is that it can perform optimality examination, quickly verifying whether digital data received is “good enough” or needs to be subjected to advanced detection. Neither the Viterbi algorithm nor the Convolutional Turbo Decoder currently offers optimality examination, a feature which will become increasingly necessary in future low complexity and energy efficient error detector design.
The LC-MLED algorithm has application in any process involving streaming of digital data, including digital cellular communication, dial-up modems, satellite and deep-space communications, computer networking and retrieval of stored data (e.g. reading hard disk drives). The LC-MLED algorithm may also be implemented in software to replace Viterbi-based systems, which are widely used in speech-to -text conversion, bioinformatics, handwriting analysis, gesture recognition, and musical score following.
