Articles
Puzzles
GK
Jobs
Connect to us Using
    Facebook Login
    Site Registration Why to Join

    Get Free Article Updates

Print Preview

Hamming Code - An Error-Correction code

+1 vote
202 views

Hamming codes are a family of linear error-correcting codes that generalize the Hamming(7,4)-code invented by Richard Hamming in 1950. Hamming codes can detect up to two-bit errors or correct one-bit errors without detection of uncorrected errors. By contrast, the simple parity code cannot correct errors, and can detect only an odd number of bits in error. Hamming codes are perfect codes, that is, they achieve the highest possible rate for codes with their block length and minimum distance.

Calculating the Hamming Code
The key to the Hamming Code is the use of extra parity bits to allow the identification of a single error.

Create the code word as follows:
1. Mark all bit positions that are powers of two as parity bits. (positions 1, 2, 4, 8, 16, 32, 64, etc.)
2. All other bit positions are for the data to be encoded. (positions 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, etc.)
3. Each parity bit calculates the parity for some of the bits in the code word. The position of the parity bit determines the sequence of bits that it alternately checks and skips.
Position 1: check 1 bit, skip 1 bit, check 1 bit, skip 1 bit, etc. (1,3,5,7,9,11,13,15,...)
Position 2: check 2 bits, skip 2 bits, check 2 bits, skip 2 bits, etc. (2,3,6,7,10,11,14,15,...)
Position 4: check 4 bits, skip 4 bits, check 4 bits, skip 4 bits, etc. (4,5,6,7,12,13,14,15,20,21,22,23,...)
Position 8: check 8 bits, skip 8 bits, check 8 bits, skip 8 bits, etc. (8-15,24-31,40-47,...)
Position 16: check 16 bits, skip 16 bits, check 16 bits, skip 16 bits, etc. (16-31,48-63,80-95,...)
Position 32: check 32 bits, skip 32 bits, check 32 bits, skip 32 bits, etc. (32-63,96-127,160-191,...)
etc.
4. Set a parity bit to 1 if the total number of ones in the positions it checks is odd. Set a parity bit to 0 if the total number of ones in the positions it checks is even.

Example:

A byte of data: 10011010
Create the data word, leaving spaces for the parity bits: _ _ 1 _ 0 0 1 _ 1 0 1 0
Calculate the parity for each parity bit (a ? represents the bit position being set):
•   Position 1 checks bits 1,3,5,7,9,11: 
? _ 1 _ 0 0 1 _ 1 0 1 0. Even parity so set position 1 to a 0: 0 _ 1 _ 0 0 1 _ 1 0 1 0
•   Position 2 checks bits 2,3,6,7,10,11:
0 ? 1 _ 0 0 1 _ 1 0 1 0. Odd parity so set position 2 to a 1: 0 1 1 _ 0 0 1 _ 1 0 1 0
•   Position 4 checks bits 4,5,6,7,12:
0 1 1 ? 0 0 1 _ 1 0 1 0. Odd parity so set position 4 to a 1: 0 1 1 1 0 0 1 _ 1 0 1 0
•   Position 8 checks bits 8,9,10,11,12:
0 1 1 1 0 0 1 ? 1 0 1 0. Even parity so set position 8 to a 0: 0 1 1 1 0 0 1 0 1 0 1 0
•   Code word: 011100101010.

The above example created a code word of 011100101010. Suppose the word that was received was 011100101110 instead. Then the receiver could calculate which bit was wrong and correct it. The method is to verify each check bit. Write down all the incorrect parity bits. Doing so, you will discover that parity bits 2 and 8 are incorrect.

posted Apr 7 by Chahat Sharma

  Promote This Article
Facebook Share Button Twitter Share Button Google+ Share Button LinkedIn Share Button Multiple Social Share Button


Related Articles

SNMP is one of the most commonly used technologies when it comes to network monitoring. Bandwidth Monitoring programs like PRTG Network Monitor use it. But how does SNMP work? What are MIBs and OIDs? Read this short introduction into the world of SNMP

SNMP Basics


SNMP stands for Simple Network Management Protocol and consists of three key components: managed devices, agents, and network-management systems (NMSs). A managed device is a node that has an SNMP agent and resides on a managed network. These devices can be routers and access servers, switches and bridges, hubs, computer hosts, or printers. An agent is a software module residing within a device. This agent translates information into a compatible format with SNMP. An NMS runs monitoring applications. They provide the bulk of processing and memory resources required for network management.

MIB, OID, etc.


MIB stands for Management Information Base and is a collection of information organized hierarchically. These are accessed using a protocol such as SNMP. There are two types of MIBs: scalar and tabular. Scalar objects define a single object instance whereas tabular objects define multiple related object instances grouped in MIB tables.
OIDs or Object Identifiers uniquely identify manged objects in a MIB hierarchy. This can be depicted as a tree, the levels of which are assigned by different organizations. Top level MIB object IDs (OIDs) belong to different standard organizations. Vendors define private branches including managed objects for their own products.

SNMP version 1 was the initial development of the SNMP protocol. A description can be found in Request for Comments (RFC) 1157 and it functions within the specification of the Structure of Management Information (SMI). It operates over User Datagram Protocol (UDP), Internet Protocol (IP), OSI Connectionless Network Services (CLNS), AppleTalk Datagram Delivery Prtocol (DDP), and Novell Internet Packet Exchange (IPX). SNMP v1 is considered the de facto network management protocol in the Internet community.

SNMP works on the basis that network management systems send out a request and the managed devices return a response. This is implemented using one of four operations: Get, GetNext, Set, and Trap. SNMP messages consist of a header and a PDU (protocol data units). The headers consist of the SNMP version number and the community name. The community name is used as a form of security in SNMP. The PDU depends on the type of message that is being sent. The Get, GetNext, and Set, as well as the response PDU, consist of PDU type, Request ID, Error status, Error index and Object/variable fields. The Trap consists of Enterprise, Agent, Agent address, Generic trap type, Specific trap code, Timestamp and Object/Value fields.

MIBs are a collection of definitions which define the properties of the managed object within the device to be managed (such as a router, switch, etc.) Each managed device keeps a database of values for each of the definitions written in the MIB. As such, it is not actually database but implementation dependent. Each vendor of SNMP equipment has an exclusive section of the MIB tree structure under their control.
In order for all of this to be properly organized, all of the manageable features of all products (from each vendor) are arranged in this tree. Each 'branch' of this tree has a number and a name, and the complete path from the top of the tree down to the point of interest forms the name of that point. This is the OID. Nodes near the top of the tree are extremely general I nature. For example, to get to the Internet, one has to reach to the fourth tier. As one moves further down, the names get more and more specific, until one gets to the bottom, where each node represents a particular feature on a specific device (or agent).

Samples Of SNMP, OIDs and MIBs:


Here is a sample structure of an OID:

Iso(1).org(3).dod(6).internet(1).private(4).transition(868).products(2).chassis(4).card(1).slotCps(2)­.-cpsSlotSummary(1).cpsModuleTable(1).cpsModuleEntry(1).cpsModuleModel(3).3562.3

or

1.3.6.1.4.868.2.4.1.2.1.1.1.3.3562.3 

These numbers are the ones used in PRTG when setting up custom sensors, in order to access the appropriate elements of the device desired to be monitored. OIDs are generally provided by the hardware manufacturers or can be found in so-called OID repositories, where collections of MIB trees and the respective OIDs can be accessed. PRTG reads these OIDs and appoints them to the pertinent device, respectively monitoring the selected device and its OID specific.

READ MORE
...