Wednesday 10 February 2016

Error Detection and correction



Hello everyone and welcome to our blog

The first week:

On Friday we read some research about hamming code from materials, lectures, videos, books and web pages and we look at some pictures, schematics and circuit diagrams. In addition, we read about the history and the advantages and the disadvantages.

Important information that we learn:

  • Richard Hamming is the person who invent hamming code in 1950.

  • The Hamming code detect and correct errors.

  • The codes are in binary.

  •  In our case the Hamming code has 7 digits 4 of them are the information bits and the other 3 are parity bits.

  • To get parity 1, 2 and 3 we use (B1+B2+B4), (B1+B3+B4) and (B2+B3+B4) respectively and when we get an even number it will equal 0 and when we get odd number it is equal to 1.

  •   In the hamming code called (7, 4) because it can encode 4 data bits into a 7 bits word.
  • From this information a logic table was created which then led to the implement of K maps. This proceeded  to the minimised expressions that was then used to create an initial design with logic gates. 
-------------------------------------------------------------------------------------------

The second week:

I downloaded LTspice and Pspice but it was difficult to simulate our project design because there was issues locating the required logic gates within the libraries. I then searched on  the Internet which led me to a program called Logisim which is simpler because it contains a large number of logic gates and also various switches. After that my partner gave me the design with a truth table illustrating the parity for each 4 bit data word. 


The truth table illustrating the parity for each 4 bit data word.


The decoder circuit design on paper.


The decoder circuit that is created by using Logisim simulator.

We built the initial design and tested it. This part of the circuit produces the required parity code for each data word, that circuit will be expanded upon to implement the error correction.

---------------------------------------------------------------------------------------

The third week:

I read some research about three types of error detection methods and I notice that:

The first type of error detection is Vertical Redundancy Check (VRC) which is also called Parity Check. This kind of error detection is used on 8-bit character. Moreover, it can be possibly used to detect bits by organised channels. It also can be used for short massages and large hamming codes. In addition, it can detect the odd errors of the data block. On the other hand, It works with an even number only, which, make this error check type unreliable.

The second type of error check is Longitudinal Redundancy Check (LRC) that depends on a parity bit that is applied and on each signal data stream blocks. In this method of detection, a table is used to organise data by making parity for each column. Furthermore, it can detect errors on each column. According to F, John this type is not effective enough comparing with Cyclic Redundancy Check (CRC).

The third part of detection method is Cyclic Redundancy Check (CRC) is one of the most effective error detection type. Because of that it can be made by a small amount of hardware and it can possibly shift registers. Additionally, this method can detect the transmitted errors on a communications link. It might be generated by a shift register feedback software.

My partner Adam designed the hamming code circuit which he tested against the logic tables to ensure correct operation. The image below is said design.


The hamming code circuit 


The red box covers four inputs on the left for the data word, the first set of lights and logic gates always ensure correct parity and by extension correct message is sent. The blue box has the next set of switches which are for the error that the logic will then correct and display in the furthest right set of lights (the yellow box).The green box illustrates the required message the user will receive.

Additionally, my partner designed and built the parity checker circuit. He firstly used K-maps but it was useless because he did not find any matches so he used the Boolean algebra to get the smallest menterm. Subsequently, he build and test the circuit. 

The K-map does not mach
Boolean Algebra equation

---------------------------------------------------------------------------------------------
 
The fourth week:

We have done the Sustainable Development and Ethics - Assignment.

I find out more about CRC. I watched a video on YouTube illustrates the method of doing CRC. We have two things that we need to work out to detect and correct the error which are word (data that is transmitted from sender to the receiver) and divisor that is given. Firstly, we look at how many number on divisor then we subtract 1 number from these numbers and we add zeros to the word that is equal to the number of divisor number after the subtraction. For example if the word equal 1101101 and the divisor equal 10101 we add 4 zeros to the divisor so it become 11011010000. After that we use the long division but with different rules. If the number start with 1 the answer is 1. Otherwise, the answer is 0 and we use Xor during the devotion As shown on the picture below.



 Subsequently, the number that appears on reminder is the error and when we replace this number with the last 4 number on the word we will get 0 reminder.


As shown on this picture the reminder is 0 after changing the last 4 bits of the word.

Look at this link for more clear description: https://www.youtube.com/watch?v=ZJH0KT6c0B0

My partner Adam researched into CRC as well.
He then designed a CRC circuit from logic that he then built on the Logisim simulator. The circuit contains a sender part that generates a three digit code via the use of XOR long division, this code is then checked against the received code and if the final result is all zeros then the message is errorless.
The correction circuit is found to be very complex and out of scope due time constraints.  
We start doing the poster.

---------------------------------------------------------------------------------------------


The fifth week:


In this week I almost finished the initial design of the poster and the blog which I then sent to Prof. Hall to check, asking him to give feedback about.

My partner has being worked hard on building the circuits to finish them as soon as possible thank you very much Adam. 
As a group we went over the poster design to implement changes as suggested by our academic adviser. 

On Monday and Tuesday;
 We did some changes on the poster and the blog depending on what the Prof. Hall mentioned on the feedback.



 





Additionally, Adam designed and build the CRC circuit.




Initial CRC circuit simulation
Final CRC circuit
Implemented circuit 1 
Implemented circuit 2