Coding Theory Case Study

What is Coding Theory? “Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding. Codes are studied by various scientific disciplines – such as information theory, electrical engineering, mathematics, and computer science – for the purpose of designing efficient and reliable data transmission methods. This typically involves the removal of redundancy and the correction (or detection) of errors in the transmitted data.” (Coding Theory, 2010) There are many aspects that go into the composition of coding theory such as error detecting, error correcting, hamming distance, perfect codes, generator matrices, parity check matrices and hamming codes all of which will be discussed here. The first two aspects, error detecting and error correcting can be studied together. When a digital message is transmitted, it is done so by a sequence of 0’s and 1’s which encodes a given message.

These messages have the potential of being corrupted by noise. Once a message is written an error-detecting code can be written into the message so that any errors can be detected and corrected before the message reaches its final destination. One of the most common types of error- detecting code is called a parity check. A parity check is “the process that ensure accurate data transmission between nodes during communication. A parity bit is appende to the original data bits to create an even or odd bit number; the number of bits with one value. The source then transmits this data via a link, and bits are checked and verified at the destination. Data is considered accurate if the number of bits (even or odd) matches the number transmitted from the source.” (Janseen, 2014) An example could be the message 1101. We add a 0 or 1 to the end of this message so that the resulting message has an even number of 1’s. We would thus encode 1101 as 11011. If the original message were 1001, we would encode that as 10010, since the original message already had n even number of 1’s. When someone receives the message 10101, since there are an odd number of 1’s, we know that an error occurred during transmission.

We do not know how many there were or which digit(s) were effected and the parity check does locate them for correction. Once the errors are located an error-correcting code can begin. An ECC “is an algorithm for expressing a sequence of numbers such that any errors which are introduced can be detected and corrected (within certain limitations) based on remaining numbers.” (Weisstein, 2014) The study of error-correcting codes and the associated mathematics is known as coding theory. Detecting the errors within codes is much easier than actually fixing the errors. The major difference between a parity check is that with error-correction, errors are detected and corrected right then, not just detected. Error correction may generally be realized in two different ways: Automatic repeat request (ARQ). This is an error control technique whereby an error detection scheme is combined with requests for retransmission of erroneous data. Every block of data received is checked using the error detection code used, and if the check fails, retransmission of the data is requested – this may be done repeatedly, until the data can be verified. The other is forward error correction (FEC).

Here the sender encodes the data using an error-correcting code prior to transmission. The additional information added by the code is used by the receiver to recover the original data. In general, the reconstructed data is what is deemed the “most likely” original data. By combining both of these concepts, minor errors are corrected without retransmission and major errors are corrected via a request for retransmission. In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In another way, it measures the minimum number of substitutions required to change one string into the other, or the minimum number of errors that could have transformed one string into the other. Some examples of the Hamming distance are: “karolin” and “kathrin” is 3, “karolin” and “kerstin” is 3, 1011101 and 1001001 is 2 and 2173896 and 2233796 is 3. The Hamming distance is named after Richard Hamming, who introduced it in his fundemental paper on Hamming codes in 1950.

Hamming weight analysis of bits is used in several disciplines including information theory, coding theory, and cryptography. Codes that attain the Hamming bound are called perfect codes. An example is given by the repeat codes, where each symbol of the message is repeated an odd fixed number of times to obtain a codeword where q=2. Hamming (7,4) is a linear error-correcting code that encodes 4 bits of data into 7 bits by adding 3 parity bits. It is a member of a larger family of Hamming codes, but the term Hamming code often refers to the code that he invented in 1950. The Hamming code adds three additional check bits to every four data bits of the message. Hamming’s (7,4) algorithm can correct and single-bit error, or detect all single-bit and two-bit errors. In other words, the minimal Hamming distance between any two correct codewords is 3, and receives words can be correctly decoded if they are at a distance of at most one from the codeword that was transmitted by the sender.

This means that for transmission medium situations where busrt errors do not occur, Hamming’s (7,4) code is effective as the medium would have to be extremely noisy for 2 out of 7 bits to be flipped. In coding theory, “ a generator matrix is a matrix whose rows form a basis for a linear code. The codewords are all of the linear combinations of the rows of this matrix, that is, the linear code is the row space of its generator matrix.” (Generator Matrix, 2014) In coding theory, “a parity-check matrix of a linear block code C is a matrix which describes the linear relations that the components of a codeword must satisfy. It can be used to decide if a particular vector is a codeword and is also used in decoding alogorithms.” (Parity-check Matrix, 2014)

Works Cited
Coding Theory. (2010). Retrieved from Wikipedia: http://en.wikipedia.org/wiki/Coding_theory Generator Matrix. (2014, May 21). Retrieved from Wikipedia: http://en.wikipedia.org/wiki/Generator_matrix Janseen, C. (2014). Parity Check. Retrieved from techopedia: http://www.techopedia.com/definition/1803/parity-check Parity-check Matrix. (2014, April 3). Retrieved from Wikipedia: http://en.wikipedia.org/wiki/Parity-check_matrix Weisstein, E. W. (2014). Error-Correcting Code. Retrieved from Wolfram MathWorld: http://mathworld.wolfram.com/Error-CorrectingCode.html