Systematic code

In coding theory, a systematic code is one in which the input data are embedded 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 corrected, 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 "010 011 010 011 010 101 010" (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 are easily recovered from received bits simply by copying the message out of the stream; redundant coded data is only required to verify that no errors have occurred, or to recover from the corruption of a message. Systematic codes have a lower bound on the size of the encoded output: the size of the original message.

Nonsystematic codes are more flexible because 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 noisy channels (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 the correctness of downloaded files.
Fountain codes, popular for online content distribution.