Error Control Coding -Introduction

ERROR CONTROL CODING - INTRODUCTION ER. FARUK BIN POYEN, Asst. Professor DEPT. OF AEIE, UIT, BU, BURDWAN, WB, INDIA faruk.poyen@gmail.com 1

Contents:  Introduction  Axioms  Types  Data Compression (Source Coding)  Error Correction Codes (Channel Coding)  Classification of Codes  Classification of Errors  Error Detection Techniques  Error Correcting Techniques  Drawbacks of coding Techniques 2

Contents: Contd….  Classification of Error – Correcting Codes  Types of Error Control  Types of Linear Block Codes  Definitions related to codes  Overview of Error Control Coding Techniques  Automatic Repeat Request (ARQ)  Forward Error Correction (FEC) Technique  Transmission Errors  Power and Bandwidth Channels  Error Detection Method  Cyclic Redundancy Check 3

Introduction:  Coding theory is one of the most important and direct applications of information theory.  It can be subdivided into source coding theory and channel coding theory.  Using a statistical description for data, information theory quantifies the number of bits needed to describe the data, which is the information entropy of the source.  Coding theory, sometimes called algebraic coding theory, deals with the design of error-correcting codes for the reliable transmission of information across noisy channels.  It makes use of classical and modern algebraic techniques involving finite fields, group theory, and polynomial algebra.  It has connections with other areas of discrete mathematics, especially number theory and the theory of experimental designs. 4

Axioms: 1. Closure of addition: if x, y are in F, then x+ y is in F. 2. Closure of multiplication: if x, y are in F, then x*y is in F. 3. Associative Law of Addition: if x, y, z are in F, then (x+ y)+z=x+(y+ z) 4. Associative Law of Multiplication: if x, y, z are in F, then (x*y)z=x(y*z) 5. Distributive Law: if x, y, z are in F, then x(y+ z)=x*y + y*z 6. Existence of 0: an element of F satisfying x+0=x for all x in F 7. Existence of 1: an element of F satisfying x.1=x for all x in F 8. Existence of additive inverses (negatives):If x is in F, there exists y in F such that x+ y=0 9. Existence of multiplicative inverses (reciprocals), except for: If x in F is not a zero element, then there exists an element y in F such that x*y=1. 10. Commutative Law of Addition: If x, y are in F, then x+ y = y+ x 11. Commutative Law of Multiplication: If x, y are in F, then x*y = y*x. 5

Types:  There are essentially two aspects to coding theory: 1. Data compression (or SOURCE CODING) 2. Error correction (or CHANNEL CODING) 6

Data Compression (Source Coding):  There are two formulations for the compression problem. 1. Loss less Data Compression: The data must be reconstructed exactly; 2. Lossy Data compression: Allocates bits needed to reconstruct the data, within a specified fidelity level measured by a distortion function. This subset of Information Theory is called Rate–Distortion Theory. 7

Error-Correcting Codes (Channel Coding):  While data compression removes as much redundancy as possible, an error correcting code adds just the right kind of redundancy (i.e., error correction) needed to transmit the data efficiently and faithfully across a noisy channel. 8

Classification of Codes: 1. Error Detecting 2. Error Correcting 3. Error Correction Techniques 9

Classification of Errors: 1. Content Error (errors in the content of message introduced due to noise during transmission). 2. Flow integrity Error (missing blocks of data, data lost in network or data delivered to wrong destination). 10

Error Detection Techniques: 1. Parity Checking 2. Check Sum Error Detecting 3. Cyclic Redundancy Check (CRC) 11

Error Correcting Techniques:  Based on generation of code words at the transmitter  Coded words contain the data bits and check bits 12

Drawbacks of Coding Technique: 1. Increased transmission bandwidth because of addition of extra bits. 2. Increased complexity of communication system. 13

Classification of Error – Correcting Codes:  Block Codes (No memory is required)  (n, k) block code is generate when the channel encoder accepts information in successive k bit blocks. At the end of each such block, (n - k) parity bit is added, which contains no information and termed as redundant bits.  Convolutional Codes (Memory is required)  Here the code words are generated by discrete – time convolution of the input sequence with impulse response of the encoder. Unlike block codes, channel encoder accepts messages as a continuous sequence and generates a continuous sequence of encoded bits at the output. 14

Another classification:  Linear Codes  Non – linear codes Linear codes have the unique property that when any two code words of linear code are added in modulo – 2 adder, a third code word is produced which is also a code, which is not the case for non – linear codes. 15

Types of Error Control: 1. Automatic Request for Retransmission (ARQ): The receiver can request for retransmission of complete or part of message, requiring additional channel called feedback channel. 2. Forward Error Correction (FEC): No feedback channel is available.  In coding theory, a linear code is an error-correcting code for which any linear combination of code words is also a code word.  Linear codes are traditionally partitioned into block codes and convolutional codes, although turbo codes can be seen as a hybrid of these two types.  Linear codes allow for more efficient encoding and decoding algorithms than other codes (cf. syndrome decoding).In coding theory, block codes comprise the large and important family of error-correcting codes that encode data in blocks.  Examples of block codes are Reed–Solomon codes, Hamming codes, Hadamard codes, Expander codes, Golay codes, and Reed–Muller codes. These examples also belong to the class of linear codes, and hence they are called linear block codes. 16

Types of Linear Block Codes: 1. Cyclic codes (e.g. Hamming codes) 2. Repetition codes 3. Parity codes 4. Polynomial codes (e.g., BCH codes) 5. Reed–Solomon codes 6. Algebraic geometric codes 7. Reed–Muller codes 8. Perfect codes 9. Single Parity Check Bit Codes 10. Repeated Codes 11. Hadamard Code 12. Extended Code 13. Goley Code 17

Important Definitions Related to Codes:  Code Word: The code word is the n bit encoded block of bits. It contains message bits and parity or redundant bits.  Block Length: The number of bits ‘n’ after coding is known as block length.  Code Rate: The code rate is defined as the ration of the number of message bits (k) to the total number of bits (n) in a code word. 𝐶𝑜𝑑𝑒 𝑟𝑎𝑡𝑒 𝑟 = 𝑘/𝑛.  Code Vector: An ‘n’ bit code word can be visualized in an n – dimensional space as a vector whose elements or coordinates are bits in the code word. 18

Important Definitions Related to Codes:  Hamming Distance: It is the distance between the two codes expressed in the number of locations in which their respective elements differ.  Hamming Weight of a Code Word [w(x)]: It is defined as the number of non – zero elements in the code word.  Code Efficiency: It is defined as the ratio of message bits to the number of transmitted bits per block. Code efficiency is equal to that of code rate.  Minimum Distance dmin: It is defined as the smallest Hamming distance between any pair of code vectors in the code. 19

Overview of Error Control Coding Techniques 20

Error Detection and Correction Capabilities Sl. No. Description Expression 1. Detect up to s errors per word 𝑑 𝑚𝑖𝑛 ≥ (𝑠 + 1) 2. Correct up to t errors per word 𝑑 𝑚𝑖𝑛 ≥ (2𝑡 + 1) 3. Correct up to t errors and detect s > t errors per word 𝑑 𝑚𝑖𝑛 ≥ (𝑡 + 𝑠 + 1) 21

Automatic Repeat Request (ARQ):  Here, when an error is detected, a request is made for retransmission of signal.  A feedback channel is necessary for this retransmission.  It differs from the FEC system in the following three aspects. 1. Less number of check bits (parity bits) are required increasing the (k/n) ration for (n, k) block code. 2. Additional hardware to implement feedback path is required. 3. But rate at forward transmission needs to make allowance for backward repeat transmission. 22

Operation of ARQ:  For each message signal at the input, the encoder produces code words which are stored temporarily at encoder output and transmitted over forward transmission channel.  At the destination, decoders decode the signals and give a positive acknowledgement (ACK) and negative acknowledgement (NAK) respectively in case no error and error is detected.  On receipt of NAK, the controller retransmits the appropriate word stored in the input buffer. 23

Operation of ARQ:  The bit rate of return transmission involving ACK/NAK transmission is lower compared to bit rate of forward transmission decreasing the probability error in return transmission to such a small value that it may be neglected.  There exists three types of ARQ systems viz. i) Stop and Wait ARQ ii) Go back N ARQ iii) Selective Repeat ARQ 24

Forward Error Correction (FEC) Technique:  It is a digital modulation system where discrete source generates information in binary form.  The channel encoder accepts these message bits and add redundant bits to them leaving higher bit rate for transmission.  Channel decoders uses the redundant bits to check for actually and erroneous transmitted messages. 25

Transmission Errors:  There are two types of transmission errors viz. random error and burst error.  Random errors are those that occur in a purely random manner. BCH codes are useful in dealing with this sort of error.  Burst errors occur in forms of bunches and are not independent. Convolution codes are not effective for this sort of errors. Fire codes which form a subclass of cyclic codes are effective in mitigating these types of errors. Interleaving is a technique which is used as an alternative for correcting burst errors. 26

Power and Bandwidth Channels:  Let the input data rate be b bits/sec.  The FEC encoder converts this into coded word at a rate of b/ R where R stands for information rate.  The M symbol modulator converts the encoder output into M possible symbol constellation having the symbol rate r_s=(b/kR) baud at the output.  Minimum system bandwidth required for successful transmission is 𝐵 = 𝑟𝑠 = 𝑏 𝑘𝑅 𝐻𝑍 27

Power and Bandwidth Channels:  The bandwidth efficiency is ƞ = 𝑏 𝑟𝑠 = 𝑘𝑅 = 𝑅 log2 𝑀 𝑏𝑖𝑡𝑠/𝐻𝑧; M = number arrays for PSK.  Band limited Channel: They have finite fixed bandwidth. Signals requiring larger bandwidths therefore cannot be transmitted over these channels without distortion. Telephonic lines come under band limited channels.  Power limited Channel: They have limited power associated with them but have large bandwidth viz. satellite channels. It is therefore possible to accommodate FEC even with increased data rate. 28

Error Detection Method:  Error correction is only possible if errors are detected in the code words. There exists many methods for error detection, the most popular ones are i) Parity Checking ii) Check sum Error Detection iii)Cyclic Redundancy Check (CRC) 29

Parity Checking:  Here an additional bit is appended with the existing message bits, known as the parity bit.  As a result of addition of this extra bit, the resultant word now will have either even or odd parity i.e. number of 1s in the code word will be either even or odd.  If it is known that the parity of the received message is always going to be even or odd as the case may be and if the received signal does not tally with the expected result, the presence of an error is detected.  The limitation of this method is that it can only detect odd number of errors and also it is unable to locate the position of the error. 30

Check Sum Error Detection:  For burst errors, parity check method is not useful.  Here then the check sum method is applied.  Here the check sum is transmitted along with every block of data bytes (8 bits).  Here an 8 bit accumulator is used to add 8 bit of a block of data to find the check sum and the carries in the MSB are discounted while finding the check sum byte.  Transmission of data byte is followed by transmission of checksum byte which is regenerated at the receiver separately by adding the received bytes.  After comparison with the transmitted byte, if results are identical it is concluded that no error has occurred otherwise there exist errors.  As byte of checksum is transmitted, there is 255 to 1 chance of detecting random error. 31

Cyclic Redundancy Check:  The concept of parity checking can be extended from detection to correction of single error by arranging the data block in rectangular matrix.  This will lead to two set of parity bits, viz. Longitudinal Redundancy Check (LRC) and Vertical Redundancy Check (VRC). 32

Longitudinal Redundancy Check:  In Longitudinal Redundancy Check, one row is taken up at a time and counting the number of 1s, the parity bit is adjusted to achieve even parity.  Here for checking the message block, a complete character known as Block Check Character (BCC) is added at the end of the block of information, which may be of even or odd parity. 33 Characters C O M P U T E R LRC bits 7 bit ASCII Codes (Message Bits) B1 1 1 1 0 1 0 1 0 1 B2 1 1 0 0 0 0 0 1 1 B3 0 1 1 0 1 1 1 0 1 B4 0 1 1 0 0 0 0 0 0 B5 0 0 0 1 1 1 0 1 0 B6 0 0 0 0 0 0 0 0 0 B7 1 1 1 1 1 1 1 1 0 VRC bits 1 1 0 0 0 1 1 1 1

Vertical Redundancy Check:  In VRC, the ASCII code for individual alphabets are considered arranged vertically and then counting the number of 1s, the parity bit is adjusted to achieve even parity.  A single error in any bit will result in a non – correct LRC in the row and a non – correct VRC in the column. The bit which is common to both the row and column is the bit in error. The limitation is though it can detect multiple errors but is capable to correct only a single error as for multiple errors it is not suitable to locate the position of the errors.  1 in the square box in the next table, is the bit in error as it is evident from the erroneous results both in the LRC and the VRC columns 34

CRC: Characters C O M P U T E R LRC bits 7 bit ASCII Codes (Message Bits) B1 1 1 1 0 0 1 0 1 (W) B2 1 1 0 0 0 0 0 1 1 B3 0 1 1 0 1 1 1 0 1 B4 0 1 1 0 0 0 0 0 0 B5 0 0 0 1 1 1 0 1 0 B6 0 0 0 0 0 0 0 0 0 B7 1 1 1 1 1 1 1 1 0 VRC bits 1 1 0 0 0 (W) 1 1 1 1 35 Advantages of LRC over VRC: i) Single errors can be detected and corrected. ii) Double and even triple errors can be detected at the cost of increased complexity. Check Sum: The bits is row b8 are character parity bits, which append to the data bits as an error checking group. These bits combining are called Checksum.

References: 1. Digital Communications; Dr. Sanjay Sharma; Katson Books. 2. Communication Engineering; B P Lathi. 36

Error Control Coding -Introduction

More Related Content

What's hot

Similar to Error Control Coding -Introduction

More from Burdwan University

Recently uploaded

In this document

Error Control Coding -Introduction