Systematic code
In Coding theory, a Systematic code is one in which the input data appears in the encoded output. Similarly, a Non-Systematic code is one in which the output does not contain the input bits. Such codes are used to add redundant information to data; this allows errors to be detected (and possibly recovered, depending on the code used) when bits are lost or corrupted.
For example, transmitting data with a checksum is a type of systematic code: to encode the bit stream "01010110" with a simple two-bit checksum, one first calculates the checksum (01+01+01+10=01), then transmits the original stream followed by the new checksum bits: "0101011001"-- note the existence of the original bits in the output. A simple nonsystematic code is Run length encoding; "01010110" might be encoded as "010011010011010101010" (one bit is zero, one bit is one, etc).
Systematic codes are typically used when the probability of loss or damage is low or transmission latency is an issue. In such cases, the original data is easy to recover from received bits simply by copying it out of the stream; redundant coded data is only required to verify receipt correctness or recover from loss/corruption of a message. Systematic codes, as they include the entire original data, have a lower bound on the size of the encoded output: the size of the original data.
Nonsystematic codes are more flexible in that all redundancy within the original bit stream can be exploited; however they tend to be more computationally complex. Often, much of the encoded bit stream must be received before any of the original bit stream can be decoded; this leads to higher latency. They are appropriate for channels with higher loss/corruption (e.g. wireless communication).
Examples of Systematic Codes
- Data + checksum, the error detection used in IP
- Reed-Solomon codes, the error correction used on CDs
Examples of Non-Systematic Codes
- Secure hashes such as SHA1 or MD5, often used to verify correctness of downloaded files
- Fountain codes, popular for online content distribution