Discrete Mathematics Project

Assigned by: Professor Manish Gupta

Subject: SC 205 -Spring 2020

Made By: Akshat Vora(201901226)

Project Topic:

Convolution Coding and its Application in Encryption

Introduction

Convolution coding is a part of Channel Coding in the process of digital communication. It is done to prevent errors while the data is being transmitted via a channel. The possible errors which take place are bit erasure and bit flipping. What channel coding does is that it introduces redundant parity bits in the signal so that the effect of those errors is minimized and the signal is received without errors.

In convolutional coding, in the encoding process only the parity bits are kept and the original signal bits are removed. This is done by a discrete finite automata. In this process, the total number of bits in the signal doubles or triple or become n times depending upon the coding scheme that we choose. After transmission, this encoded stream of bits must be decoded back to the original message. This is done by the Viterbi Algorithm.

Finally, I have used the process of convolution coding and with a few modification to it, made an encryption system. The details for each of the above-mentioned are given the the documents attached.

More About Convolution Codes

For any channel coding scheme, the encoding part is easier compared to the decoded part. Same is true for Convolution codes. To decode the coded sequence of bits, we use the Viterbi Algorithm. It is dependent on calculating branch metrics and path metrics. The branch metric is nothing but the the difference in the expected bit sequence and the received bit sequence for one given time and a given pair of states. The sum of those branch metrics for a given path is its path metric. We choose the path which has the lowest path metric and then trace back the bits which would have been there in the original sequence.

Images Describing Some Aspects of Encoding and Decoding

Encoding via DFA

Calculation of Branch Metric

The above DFA is the simplest way to encode a given code with one of the simplest convolution schemes which is K=3, rate =1/2. On the arrows, the input bit for that state along with the corresponding output parity bits is given.

The above diagram is one of the simplest representation of calculating branch metric for K=3, rate =1/2. The digits marked in red on the time axis denote the bits received at that instant and the ones on the arrows represent the branch metric for that branch at that time.

More About Encryption

Encryption is the conversion of data into a form that can be translated a specific set of people who have the key to decode it. This can be done in many ways like by changing the characters, removing certain characters in a pattern, or by adding new characters by by a combination of any or all of the above. Encryption can vary in levels of security. Caesar's encryption is one of the most basic forms of encryption in which every alphabet is replaced by another alphabet which is 3 alphabets after that. So A is replaced by D, M by P etc. This is very easy to decode without knowing the rule behind encrypting. Many more secure encryption methods have been developed.

The encryption model used in the project encrypts any 7 bit ASCII characters. This model is much more secure than the models like Caesar's encryption and many more.

Further Links Related to the Project

201901226.pdf

Other documents related to the project can be found here.

The code for the project can be found here.

Page updated

Google Sites

Report abuse