22-08-2014, 12:17 PM
HAMMING CODE
HAMMING CODE.docx (Size: 1.03 MB / Downloads: 14)
Abstract:
Hamming Codes are used in detecting and correcting a code. An error-correcting code is an algorithm for expressing a sequence of numbers such that any errors which are introduced can be detected and corrected (within certain limitations) based on the remaining numbers. Errors can happen in a variety of ways. Bits can be added, deleted, or flipped. Errors can happen in fixed or variable codes. Error-correcting codes are used in CD players, high speed modems, and cellular phones. Error detection is much simpler than error correction. For example, one or more "check" digits are commonly embedded in credit card numbers in order to detect mistakes. The process of hamming code shows how to detect and correct an error in a code.
Here the alphabets will be finite fields. Linear codes with length n and dimension k will be described as [n, k] codes. Hamming Codes are linear codes, and a Hamming Code will be described as a [n, k] q- ary Hamming Code, where q is the size of the base field, Fq. In other words an [n,k] q- ary Hamming Code is a linear subspace of the n-dimensional vector space over Fq.
In this paper, we give two unexpected applications of a Hamming code. The first one, also known as the "Hat Problem," is based on the fact that a small portion of the available code words are actually used in a Hamming code. The second one is a magic trick based on the fact that a Hamming code is perfect for single-error correction
INTRODUCTION :
One of the major issues in the field of communication is the secure and error free transmission of data from transmitter to receiver. And for error free transmission there are number of technologies. One of the technologies which is used for correcting forward error is the Hamming code technology. Around 1947 Richard W. Hamming developed this technology to detect and correct single bit errors in transmitted data. In Hamming code error detection and correction technique to get error free data at destination, we encrypt information data according to even and odd parity method before transmission of information at source end.[3][1]
In telecommunication, Hamming codes are a family of linear error correcting codes. Hamming codes can detect upto two and correct upto one bit errors. By contrast the simple parity code cannot correct errors, and can detect only odd number of errors. Hamming code are special in that they are perfect codes, that is they achieve the high test possible rate for codes with their block length and minimum distance. Because of the simplicity of hamming codes, they are widely used in computer memory. In this context one often uses an extended hamming code with one extra parity bit. Extended hamming code achieve a distance of 4, which allows the decoder to distinguish between the situation in which at most one bit error occurred and the situation in which two bit error occurred. In this sense, extended hamming codes are single error correcting and double-error detecting and often reffered to as SECDED.[3][4] In this paper we have written Verilog code for finding error location and correct the bit which is corrupted. At the destination, we receive 7-bit of data with 4 redundancy bits. This received data may be corrupted due to noise. To remove this noise we find the address of the error bit then correct them. To find the location of error bit and correct them we write code in Verilog language.This paper is organized as follows, the concept of hamming code along with the application of it, Verilog language, Why Verilog is preffered over VHDL, Implementation of hamming code, Performance and experimental results, conclusion and references
. HAMMING CODE :
Hamming code are the linear block code which are invented by Richard. W. Hamming. They are an improvement over simple parity code method. Hamming codes are valid only when the hamming distance between the bits is less then or equal to one. By contrast, the simple parity code cannot correct errors, and can only detect an odd number of errors. They are the type of binary codes. The idea of hamming distance is the central concept in coding the error control. The hamming distance between the two words (of the same size) is the number of differences between the corresponding bits. The hamming distance can easily be found if we apply the Xor operation on the two words and count the number of 1s in the result. The hamming distance is a value always greater then zero. If we find the hamming distance between any two words it will be the result of the Xoring of the two bits. Like the hamming distance between d (000,011) is 2 because 000 xor 011 is 011(two 1s) and the hamming distance between d(10101,11110) is 3 because 10101 xor 11110 is 01011(three1s). Hamming code method works only on two methods(even parity, odd parity) for generating redundancy bits. The number of redundancy bits are generated using a formula. The number of redundancy depends on the number of information data bits. The formula is:
. USING VERILOG FOR SIMULATION
The basic structure of Verilog in which all hardware components and testbenches are described is called a module. Language constructs, in accordance to Verilog syntax and semantics form the inside of a module. These constructs are designed to facilitate the description of hardware components for simulation, synthesis, and specification of testbenches to specify test data and monitor circuit responses. A module that encloses a design’s description can be described to test the module under design, in which case it is regarded as the testbench of the design
PERFORMANCE AND EXPERIMENTAL RESULT
We have written a code in verilog for hamming [7,4] code. The code is running successfully. In this code we are initializing adata of 4 bit and calculating its parity bit by the above general algorithm. It requires to calculate the parity bit by matrix multiplication and modulo-2 addition. The parity bit required for four bit data is three bit. These bits are calculated and the code is written using case statement. We have done encoding and decoding of the data in the same code. A variable syndrome is used to decode the data and to calculate the parity bit. Syndrome is calculated by multiplying a 3x7 matrix[H] by a 7x1 matrix representing the encoded data produces a 3x1 matrix, called ‘syndrome’. The syndrome has two useful properties. First if the syndrome is all zeros, nonzero value, then flip the encoded bit that is in the position of the column in [H] that matches the syndrome will result in a valid code word.[6] Before viewing the test bench waveform we will show the input/output ports of hamming encoder and decoder
. CONCLUSION
Thus we have tried to implement hamming code in verilog language and shown the output results. Hamming codes have improved the way of communication by detecting and correcting errors. We have also given the reason that why we are preffering verilog language over VHDL.