What is Coding Theory?  

Code is an alternative representation of some information—like a word, image, sound, and so on—that follows a set of rules. While  coding theory may refer to the practice of studying such codes and their applications, in recent years, the term pertains to error-correcting codes.  

The use of communication technologies has seen rapid growth over the last few decades. A profuse amount of data is being sent and received all across the globe each day. Since communication channels (like cables, phone lines, even the atmosphere) are typically noisy, the data sent across them needs extra protection. Coding theory uses many algebraic concepts to ensure the same.  

What is a Channel?  

A channel is a physical or logical pathway of communication. It helps transfer information between two or more points. In a communication system, the data source is the origin of the data, while the data sink is its destination.  

A wire is an example of a physical channel. Wires are present in telecom circuits that provide one or many communication channels between two or more points.  A logical channel would be a computer network. While we cannot physically see this channel, its purpose is still to transmit an information signal over multiple points (multiple computers, in this case).  

What is Noise? 

A common problem that teachers face is trying to be audible over all the voices of their students. In this case, their channel (the air around them) is noisy. In a communication system, any signal that interferes with the information signal is called noise. These signals could originate from many sources, both natural and man-made.  

Natural signals are randomly produced by some external, natural phenomenon. Some examples are the sounds of a thunderstorm, poor lighting, and the unavoidable thermal motion of electrons (thermal noise).  

Man-made noise, however, usually comes from a piece of equipment. It could be an electrical or electromagnetic signal that obstructed the necessary signal. This type of noise can be lessened by using corrective algorithms.  

Classification of Coding 

While coding can mean any number of things, concerning coding theory, there are three main fields to focus on: 

• Data Compression: Otherwise known as source coding, it deals with encoding the source data to require less space in comparison. This process reduces the number of bits needed to represent the original information. There are two methods of data compression: by using either lossy or lossless algorithms.   

• Error control: Also known as channel coding; this type of coding concentrates on making transmission over noisy channels as reliable as possible. It makes sure that the necessary information reaches the recipients error-free. While source coding deals with making information as small as possible, channel coding deals with expanding data.  

• Cryptographic coding: Cryptography ensures data security. It makes sure that a required piece of information does not end up in the wrong hands. The difference between cryptography and error control is that the former deals with information confidentiality while the latter deals with information clarity. Cryptography guarantees that the data only reaches the expected recipient, while error control makes the data decodable despite interference in the channel.  

Channel Coding: Error Detection and Correction 

Coding theory is known as the theory of error-correcting codes. One of its applications is facilitating the transfer of digital data over a communication channel despite disruptions. This process takes place in two phases:  

• Error Correction: Revives the original data by eliminating or minimizing interferences  

• Error Detection: Detects interferences in the original data  

Error Correction: 

1. Automatic Repeat Request (ARQ) 

Also known as backward error correction, this mechanism works using acknowledgments. When the receiver acquires a message, it sends an acknowledgment to let the transmitter know of its status. But if the transmitter does not receive the acknowledgment before a timeout limit, it resends the message to the receiver. The problems with this technique are the increase in latency (delay between the transmitter and receiver) and the necessity for additional memory and a timer.  

The types of ARQ protocols are: 

• Stop-and-wait ARQ: One data frame is sent at a time, after which the sender waits for the acknowledgment. If it doesn’t acquire one before the timeout, then it resends the same data frame.  

• Go-Back-N ARQ: N is the transmitter’s window size. So, it can send an N-number of data frames before waiting on the receiver’s acknowledgment.  

• Selective Repeat ARQ: Even after a frame is lost, this protocol keeps sending frames for a particular window size. Only after this window size is exhausted will the sender respond to the receiver’s lost frame. A sequence number is assigned to the unacknowledged data frame so that the transmitter can resend it after it has finished sending out frames within its window size.   

2. Forward error correction 

Forward error correction adds redundant data to the message sent. Therefore, if the message is corrupted, the receiver can retrieve the data. This method also avoids the time-consuming process of sending and receiving acknowledgments.  

There are two major categories of FEC: 

• Convolutional codes: The message is split into blocks of a certain size. Redundancy is added to all the individual blocks.  
• Block codes: An error-correcting code that acts on k input data bits to produce n output data bits.  

Error Detection: 

To help us detect any interruptions or errors in the required data due to a noisy channel, we add additional data whenever we choose to transmit. This added data is the error-detecting code.  

Some popular techniques for error detection are: 

• Simple Parity: A check bit or parity bit is included in the blocks of data. The number 1 is added to the block in case it contains an odd number of 1s, and 0 is added in the case of an even number of 1s.  

• Two-dimensional Parity: In this case, the data is treated as rows and columns. Parity is calculated for each row and column. The original data and the data with parity bits are both sent to the receiver.   

• Checksum: It handles segments of data of a certain length. These segments are added up using ones’ complement operations. The result is complemented to get the checksum. The checksum is now considered as one of the data segments, and all the segments are sent to the receiving end, where the same operations are performed. If the result is zero, then the correct data has reached its destination.  

• Cyclic redundancy check: This method is based on binary division. Cyclic redundancy check bits are calculated and attached to the end of the data. The result should be perfectly divisible by another fixed binary number. This number is known by the receiver as well so that when the data reaches its side, it can perform the same division operation. If there is no remainder, the receiver can determine that it has acquired an error-free version of the source data.   

Context and Applications: 

This topic is significant in the professional exams for both undergraduate and graduate courses, especially for       

• BCA 
• B.Sc. Computer Science 
• M.Sc. Computer Science