What is Logic gates

A logic gate is a collection of transistors and other electronic components that make up a Boolean logical operation, such as AND, NAND, OR and NOR. Transistors make up logic gates. Logic gates make up circuits. Circuits make up electronic systems.

What is Hamming Code and how can it work And how can you detect and correct an error

In data communications, Hamming code is an error detection code that is interspersed with the bits of each character. At the receiving station, the code is checked in order to detect missing bits, and one-bit errors can be corrected automatically.

Hamming is a code is used to detect and correct errors in individual bits of transmitted data. Most land-based communications are satisfied by relying on checksum or CRC methods to detect errors. CRC correction requires re-transmission of faulty messages. But let us take the case of a satellite transmitting visual data as binary streams of information around another planet say Jupiter. The time it takes those messages to arrive at an Earth station from the satellite is measured in hours. During this time the satellite has adjusted its orbit and is going across new territory and sending additional data. Correcting errors in these messages cannot be done by re-transmission. A request for that re-transmission takes as long to get to the satellite as the original message took to get to Earth. Then consider the time it would take to resent the message. First satellite would have to be found. During the time it looks to send the original message and get the request to resent it, the satellite has gathered billions of additional data. The memory needed to hold data long enough to assure that were sent properly is staggering. Instead, an error-correction method such as the Hamming code is used so that errors can be corrected as they are detected.

             Hamming code provide a method for error correction. Error bits called Hamming bits, are inserted into the message at the random locations. It is believed that the randomness of their locations reduces the odds that these Hamming bits themselves would be in error. This is based on a mathematical assumption that because there are so many more message bits compared with hamming bits, there is a greater chance for a message bit to be in error than for a Hamming bit to be wrong. Determining the placement and binary value of the Hamming bits can be implemented using hardware, but it is often more practical to implement them using software. The number of bits in a message (M) are counted and used to solve the following equation to determine the number of Hamming bits (H) to be used.

 2^H ≥ H + M + 1

Once the number of hamming bits is determined, the actual placements of bits into the message are performed. It is important to note that despite the random nature of the hamming bit placements, exact placements must be known and used by both the transmitter and receiver.

This is necessary so that the receiver can remove the Hamming bits from the message and compare them with a similar set of bits generated at the receiver. Once the hamming bits are inserted into their positions, the numerical values of the bit positions of the logic 1 in the original message are listed. The equivalent binary numbers of these values are added and the sum produced is used as the sets of the Hamming bits in the message. The numerical difference between the Hamming values transmitted and that produced at the receiver indicates the bit position that contains a bad bit which is then inverted to correct it.

        We shall see the following example for sending the message Help!

        When sending the message Help! using synchronous data, start and stop bits as well as parity are not used. Each ASCII character contains 7 bits, for a total of 35 bits. The number of hamming bits is computed using equation

                     2^H ≥ H + M + 1

     H = 6 is the smallest value that satisfies the equation.

                    64 > 35 + 6 + 1 > 42

    For simplicity we will insert the Hamming bits, less randomly, at every other bit position, starting with the least significant bit:

                   H  e  l  p  !

100100011001011101100111000001H0H0H0H0H1H

To begin the process of determining the states of each of the Hamming bits, list of numerical value of each bit position whose state is a 1. Start with the least significant bit as 1 and increase the count by 1 for each succeeding bit position. H bit must be included in the counting (but not the listing) process. In our example, the first bit position with a 1 in it is position 2. The following are all the bit positions containing a 1 that is the positions 2, 12, 18, 19, 20, 23, 24, 26, 27, 28, 30, 33, 34, 38, and 41.

      The next step is to list the number of vertically along with the binary equivalent of each one. The value of the Hamming bits (H) is created by adding each binary bit column in the list, ignoring any carry condition.

2     0 0 0 0 1 0

12   0 0 1 1 0 0

18   0 1 0 0 1 0

19   0 1 0 0 1 1

20   0 1 0 1 0 0

23   0 1 0 1 1 1

24   0 1 1 0 0 0

26   0 1 1 0 1 0

27   0 1 1 0 1 1

28   0 1 1 1 0 0

30   0 1 1 1 1 0

33   1 0 0 0 0 1

34   1 0 0 0 1 0

38   1 0 0 1 1 0

41   1 0 1 0 0 1

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

H = 0 1 1 0 1 1

These values are submitted for the "H" bits in the message in the order shown. The receiver repeats the process, again ignoring the Hamming bit positions in the list. If everything is all right, a comparison of the H values sent and those generated by the receiver produces zero. When the receiver does the Hamming process, number 23 is omitted from the list. This causes the Hamming bits to have a value of 0 0 1 1 0 0 instead of 0 1 1 0 1 1. When the H bits computed at the receiver are compared with the transmitted H bits the result is as follows :

 H sent                             0 1 1 0 1 1     as shown above

 H computed at receiver  0 0 1 1  0 0 *

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

comparison results:          0 1 0 1 1 1 = 23 decimal

* because 23rd 1 will be changed to zero so the sum !

To correct the message the receiver would invert bit 23.

The reason why the Hamming code works is as follows:

     The originally transmitted codes are formulated by adding binary bits together, ignoring carries. The process of this addition is nothing more than exclusive ORing these bits together. A similar process occurs at the receiver. If a bit has changed state between being sent and  received , it either will not be included in the process or , in the case of changing from a 0 to a 1, will be added to the process. By exclusive ORing the two Hamming codes, the process is reversed. The errant bit appears as the difference between the transmitted and received Hamming bit values.

CHECKSUM ERROR DETECTION

Checksum is a calculated value that is used to test data integrity. Errors can occur when data is transmitted or when it is written to disk. One means of detecting such errors is use of a checksum. Checksum is a value calculated for a given chunk of data by sequentially combining all the bytes of data with a series of arithmetic or logical operations. After the data is transmitted or stored, a new checksum can be calculated (using the possibly faulty transmitted or stored data) and compared with the original one. If the checksum do not match, an error occurred, and the data should be transmitted or stored again. If they do match, the transmission or storage was probably error-free. Checksums are simple validation mechanism. They cannot detect all errors and they cannot be used to correct errors.

            The parity and LRC methods are not very reliable, when more than error occurs within a character or message. One major advantage of the CRC method is its ability to detect multiple errors within any length of message.

             Another major advantage of checksum is that it is simple to implement. In this method, each character being transmitted is exclusive ORed with an accumulated total of all previous characters. The final accumulated total is the checksum character sent with the message. Once again, at the receiver exclusive ORing all the characters and the transmitted checksum should produce a result of zero. Any other result indicates that an error has occurred.

             In comparison with CRC, checksum is more likely to experience similar values for different messages. While the odds that enough errors would cause a duplicate checksum to the one originally sent are reasonable high, that possibility is still far more likely than a similar occurrence using the CRC method.

See More -- 

                Cyclic Redundancy check 

CYCLIC REDUNDANCY CHECK (CRC)

CYCLIC REDUNDANCY CHECK (CRC)

In synchronous communications, CRC is used to verify the integrity of the entire packet or block of data. Integrity of the packet means whether the complete packet of data received in its correct form as it was sent from the sending end. In synchronous communications, parity checking is sufficient to ensure data integrity. In high-speed asynchronous communications, single bit corrections are not enough. As each packet is created, a CRC check is placed somewhere in the packet and is verified at the receiving end.

            CRC is a calculation method used to check the accuracy of a digital transmission over a communication link. The sending computer uses one of several formulas to calculate a value from the information contained in the data, and this value is appended to the message block before it is sent. The receiving computer performs the same calculation on the same data and should drive the same number. If the two CRCs  do not match, indicating that a transmission error has occurred, the receiving computer asks the sending computer to retransmit the data.

            This procedure is known as redundancy check because each transmission includes extra or redundant error-checking values as well as the data itself. A CRC is generated by dividing the total number of bits in the block of data being sent by a predetermined binary number. The reminder is then added to the packet and the packet is transmitted. On the receiving end, the reverse mathematical operation is performed to verify the packet contents. If the computation is successful, the packet is passed to the next step. If it fails, the issuing node is notified and the entire packet is re-transmitted.

            Common CRC patterns are 12-bit (CRC 12), 16-bit (CRC 16), and 32-bit (CRC 32).

One of the most common and widely used error detection methods for synchronous data transmission is Cyclic Redundancy Check (CRC), developed by IBM. IBM uses CRC-16 as the specific application of the CRC method. This process uses a constant "divisor" which is in binary form as ::

                          1000 1000 0001 0000 1

The steps are follows :

(a) Add 16 zeros (1 less bit than the number of bits in the "divisor") after the Least Significant Bit of the message to be sent. The message is then written down as it would be transmitted, with the extra bits sent first ( i.e. most significant bits).

(b) The divisor is exclusive ORed with the 16 most significant bits of the message are appended to the result of this to from another 16 bits of data headed by a 1.

(c) The exclusive ORing is repeated along with the rest of the process until all bits in the message are exhausted.

(d) The final exclusive OR result is the CRC characters. Enough leading zeros are appended to the CRC character to from a total of 16 bits.

           We shall try to understand the CRC character calculation using the following CRC-4 method with the modified divisor constant of 10011:

          Let the message be 1100 0110 1011 01 (The LSB is on the right)

          There is one less zero than the total number of bits in the divisor which is 10011. To use the shortened CRC-4 divisor, four zeros are

first appended to the message. The extended message becomes:

      

       110001101011010000

       Now we set up the problem:

       10011)110001101011010000

       

       Exclusive OR the first five bits with the "divisor" we have:

 

       10011)110001101011010000

             10011

             -----------

               1011

By bringing down the next bit from the message and repeating the process until all the bits in the appended message are used.

     We do this as shown below:

     10011)110001101011010000

           10011

           ----------

            10111

            10011

            ----------

             10010

             10011

             ----------

              11011

              10011

              ----------

               10000

               10011

               ----------

                 11100

                 10011

                 ----------

                  11110

                  10011

                  ----------

                   11010

                   10011

                   ----------

                     1001 = CRC

The original message followed by the CRC-16 bytes is sent to a receiving station. At the receiving station, the data are shifted in and a CRC is computed using the entire message plus the CRC bytes. If the same constant "divisor" is used, the result of the receiver's CRC computation is all zeros when there are no errors.

             To detect the correct communication errors, a sender must provide a receiver with information that enables the receiver to verify proper receipt of information or data. The sender could simply send an entire set of information twice and let the receiver compare the two sets of information for error detection, but because of the time and computer resources, it takes to perform this type of comparison. It is more popular to detect the error based on mathematical calculations that are hardware or software execute at high speed.

              The sender must use a mathematical technique to calculate error-checking data. The sender generates this redundancy data from the bit stream of information data from the bit stream of information data it sends and then appends the redundancy data to the end of the bit stream. The receiver must generate its own redundancy data from the information data it receives and compare the results with the redundancy data it receives from the sender. A favourable comparison indicates the absence of errors. An unfavourable comparison indicates the presence of errors.