Error Control and Block Codes PDF

Module #7 Error Control and Block Codes Error Detection Error Correction Error Detection and Correction Can be addressed by using Error Correction Codes (ECC) ECC are techniques that enable reliable delivery of digital data over unreliable communicatio...

Module #7 Error Control and Block Codes Error Detection Error Correction Error Detection and Correction Can be addressed by using Error Correction Codes (ECC) ECC are techniques that enable reliable delivery of digital data over unreliable communication channels. Many communication channels are subject to channel noise, and thus errors may be introduced during transmission from the source to a receiver. Error detection techniques allow detecting such errors. Error correction enables recovery of the original. Error Detection Codes This techniques are primarily used for detecting errors only. Repetition codes Parity Checks Vertical Redundancy Check (VRC) Longitudinal Redundancy Check (LRC) Cyclic Redundancy Check (CRC) Checksums Cryptographic Hash functions Etc. Repetition Codes The very basic and primitive error detection code. The idea of the repetition code is to just repeat the message several times. The assumption is that the channel corrupts only a minority of these repetitions. This way the receiver will notice that a transmission error occurred since the received data stream is not the repetition of a single message, and moreover, the receiver can recover the original message by looking at the received message in the data stream that occurs most often. Example: Repetition = 3  Parity Check (Vertical Redundancy Check) A parity bit, or check bit is a bit added to the end of a string of binary code that indicates whether the number of bits in the string with the value one is even or odd. Parity bits are used as the simplest form of error detecting code. There are two variants of parity bits: even parity bit and odd parity bit. Even parity : for a given set of bits, the occurrences of bits whose value is 1 is counted. If that no. of 1’s is odd, the parity bit value is set to 1, making the total count of occurrences of 1's in the whole set (including the parity bit) an even number. If the count of 1's in a given set of bits is already even, the parity bit's value remains 0. Odd parity : reversed compared to Even parity. See Tutorial Video on VRC! Parity Check (Longitudinal Redundancy Checks) Utilizing parity bits on a block of binary data stream. Also called horizontal redundancy check.  Parity Check (Cyclic Redundancy Check: CRC) A technique for detecting errors in digital data, but not for making corrections when errors are detected. In the CRC method, a certain number of check bits, often also called a checksum or frame check sequence (FCS), are appended to the message being transmitted. The receiver can determine whether or not the check bits agree with the data, to ascertain with a certain degree of probability whether or not an error occurred in transmission. The CRC is based on polynomial arithmetic, in particular, on computing the remainder of dividing one polynomial by another polynomial. Binary Polynomial Arithmetic Example: Binary Polynomial Division Formulation of CRC Sample CRC calculations: See Tutorial Video on CRC!  Checksum A checksum of a message is a modular arithmetic sum of message code words of a fixed word length. The sum may be negated by means of a ones'-complement operation prior to transmission to detect errors resulting in all-zero messages. See Tutorial Video on Checksums!  Cryptographic Hash Functions (CHF) Is a hash function which is considered practically impossible to invert, that is, to recreate the input data from its hash value alone. The values returned by a hash function are called hash values, hash codes, hash sums, or hash digest. Hashing is the transformation of a string of characters (data) into a fixed-length value or key that is represented as the original string.  Hashing Properties of an ideal Hash algorithm: a.) it is quick to compute the hash value for any given data b.) it is infeasible to retrieve the data from its hash c.) it is infeasible to modify a data without changing the hash d.) it is infeasible to find two different data with the same hash Practical use of CHF: Storing passwords as plain text can result in a security breach if the password file is compromised. To reduce this danger, only store the hash of each password. To authenticate a user, the password presented by the user is hashed and compared with the stored hash. (Note that this approach prevents the original passwords from being retrieved if forgotten or lost, and they have to be replaced with new ones. That is why in most websites, if you forgot your password, you are requested to reset and create a new one, instead of giving you the original password.) See Tutorial Video on Hashing Algorithms! Hashing Algorithms Forward Error Correction (FEC) Also known as error-correcting codes (ECC). Classification of FEC/ECC: Convolutional codes are processed on a bit-by-bit basis. Convolutional encoder (discussed in Module #6) Viterbi decoder (discussed in Module #9) Block codes are processed on a block-by-block basis. (“block” = group of bits) Repetition codes Hamming codes Multidimensional parity-check codes (CRC, VRC, LRC) Checksums Reed–Solomon codes Etc. Error Correction Methods Use Automatic Repeat reQuest (ARQ) (sometimes also referred to as backward error correction): 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. Use Forward error correction (FEC) The sender encodes the data using an error-correcting code (ECC) 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. ARQ and FEC may be combined, such that minor errors are corrected by FEC, and major errors are corrected via ARQ:  ARQ Also known as Automatic Repeat Query, uses: acknowledgements =messages sent by the receiver indicating that it has correctly received the data timeouts = specified periods of time allowed to elapse before an acknowledgment is to be received -If the sender does not receive an acknowledgment before the timeout, it usually re- transmits the frame/packet until the sender receives an acknowledgment or exceeds a predefined number of re-transmissions. Types of ARQ protocols include Stop-and-wait ARQ Go-Back-N ARQ Selective Repeat ARQ These protocols reside in the Data Link or Transport Layers of the OSI model.  Stop-and-Wait ARQ After sending each frame of data, the sender doesn't send any further frames until it receives an acknowledged (ACK) signal. After receiving a good frame, the receiver sends an ACK. In some cases, it will send a NACK (not acknowledged) signal. If the ACK does not reach the sender before a certain time, known as the timeout, the sender sends the same frame again. Timer is reset after each successful frame transmission. This is the simplest Stop-and-Wait implementation.  Go-Back-N ARQ The sending process continues to send a number of frames specified by a window size even without receiving an acknowledgement (ACK) packet from the receiver. It can transmit N frames to the peer before requiring an ACK. The receiver keeps track of the sequence number of the next frame it expects to receive, and sends that number with every ACK it sends. The receiver will discard any frame that does not have the exact sequence number it expects (either a duplicate frame it already acknowledged, or an out- of-order frame it expects to receive later) and will resend an ACK for the last correct in-order frame. Once the sender has sent all of the frames in its window, it will detect that all of the frames since the first lost frame are outstanding, and will go back to the sequence number of the last ACK it received from the receiver process and fill its window starting with that frame and continue the process over again. Selective Repeat ARQ The receiver process keeps track of the sequence number of the earliest frame it has not received, and sends that number with every acknowledgement (ACK) it sends. If a frame from the sender does not reach the receiver, the sender continues to send subsequent frames until it has emptied its window. The receiver continues to fill its receiving window with the subsequent frames, replying each time with an ACK containing the sequence number of the earliest missing frame. Once the sender has sent all the frames in its window, it re-sends the frame number given by the ACKs, and then continues where it left off. Selective Repeat ARQ  Hamming Code The American mathematician Richard W. Hamming pioneered this field in the 1940s and invented this first- ever error-correcting code in 1950. Hamming(7,4) is a linear error-correcting code that encodes four bits of data into seven bits by adding Bit Parity Coverage three parity bits. It is a member of a larger family of Hamming codes, but the term Hamming code often refers to this specific code that Richard W. Hamming developed. The Hamming code adds three additional check bits to every four data bits of the message. Hamming's (7,4) algorithm can correct any single-bit error, or detect all single-bit and two-bit errors. Check bits are determined by using even parity. Bit position  Hamming Codes (General Rule) Number the bits starting from 1: (bit 1, 2, 3, 4, etc.) Bit positions that are powers of 2 will be the parity bits: (bit 1, 2, 4, 8, etc.) All other bit positions will be the data bits. Bit Parity coverage: see Hamming Table below. Common Examples: Hamming (7,4) Hamming (15,11) Hamming (12,8) Hamming (21,16)  From Hamming Table Hamming Code (7,4) Problem: Parity Equations Find the 7-bit code word for (short-cut) transmitting the data = “1010” P1 = D4⊕D2⊕D1 using Hamming Code (7,4) P2 = D4⊕D3⊕D1 P3 = D4⊕D3⊕D2 Solution: (long-method) Using Matrices: Given: (1010)2 = D4D3D2D1 P1 = 1⊕1⊕0 P2 = 1⊕0⊕0 P3 = 1⊕0⊕1 D1=0 D2=1 P1 = 0 D3=0 Next ANS = 1010010 P2 = 1 page D4=1 P3 = 0 Solution (Continued): ANS: “1010010” How Error is Detected? Problem: Check if the data word “1010010” contains errors if it uses Hamming(7,4) codes? Given: Solution: How Error is Located? Problem: Check if the data word “1110010” contains errors if it uses Hamming(7,4) codes? Given: We “flipped” bit-6 (0→1) Solution: Error in bit #6 compare ANS: result with hamming matrix  Reed-Solomon Codes (RS codes) Reed–Solomon codes are an important group of error-correcting codes that were introduced by Irving Reed and Gustave Solomon in 1960. The key idea behind a Reed-Solomon code is that the data encoded is first visualized as a polynomial. The code relies on a theorem from algebra that states that any k distinct points uniquely determine a polynomial of degree at most k-1. The polynomial is then "encoded" by its evaluation at various points, and these values are what is actually sent. During transmission, some of these values may become corrupted. Therefore, more than k points are actually sent. As long as sufficient values are received correctly, the receiver can deduce what the original polynomial was, and decode the original data. Today RS codes are used in hard disk drive, DVD, telecommunication, and digital broadcast protocols. RS codes needs computers or specific hardware to implement, since involves complex matrix manipulations. It cannot be easily simulated manually. See Tutorial Video on RS Code applications!