Hamming Code Error Detector/Decoder
 
 

Students: Jennifer Dilliner and Melissa DePriest

Advisor: Dr. Vinod Prasad
 
 
 
 
 
 
 

EE 451 Senior Design Project Proposal

December 14, 2001





 
 

View:
            - Project Summary
            - Detailed Description
            - Basic Block Diagram
            - Complete Block Diagram
            - System Inputs and Outputs
            - Complete System
            - Subsystem Inputs and Outputs
            - Datasheet
            - Equipment and Parts Needed
            - Tentative Schedule
            - Patents
            - References
 
 
 
 
 
 
 
 
 
 

Back

Project Summary

The Hamming Code Error Detector/Decoder chip will be designed based on a reliability concept called (7,4) Hamming Code. The chip will accept a seven-bit code word, the b-vector, and determine if the signal contains any errors utilizing a three-by-seven binary matrix, the H-matrix. The b-vector contains seven bits of information and three parity check bits and the H-matrix is predetermined. This chip will be able to detect up to two errors and correct one error within the b-vector. If an error is detected, a signal will be sent back requesting that the vector be resubmitted. If no errors are detected, the code word will be decoded and the four-bit information word will appear on the output pins.

Initially, the circuit will be designed at the gate level utilizing LogicWorks. Then the circuit will be implemented into VLSI using L-edit. If time permits, the gate level circuit will be translated into VHDL code for implementation onto an FPGA chip.
 
 

Back

Detailed Description

The chip will consist of several inputs and outputs. It will accept the seven-bit b-vector from an outside source. This input vector will be stored in a seven-bit register. In addition to this, the H-matrix will be formed using three supplementary seven-bit registers. Three seven-bit error-checking vectors will be input to these registers and held by twenty-one tri-state devices (three sets of seven). The basic block diagram (Figure 1), complete block diagram (Figure 2), and the tables for the subsystems (Tables 1 and 2) on the following pages will help clarify this description.

Each of the tri-state devices will be controlled by circuitry which will allow the data to be released (seven bits at a time) as required in the error detection process. The H-matrix and the b-vector will be multiplied to form the three-bit S-vector. This vector will indicate if the b-vector input to the system is corrupt or correct.

If the b-vector is corrupt, a signal will be transmitted back to the source to indicate the need for retransmission of the data. However, if the S-vector indicates that the b-vector is not corrupt, the b-vector will be sent through decoding circuitry and the four-bit decoded data will appear on the output.
 

Figure 1: Basic Block Diagram

Figure 2: Complete Block Diagram




Back
 

Inputs Description
  b-vector Seven-bit signal to be analyzed (output from source)
  H-matrix Three seven-bit error-checking vectors 
Outputs
  Error signal  Signal to source indicating an error within the b-vector
  Decoded vector Four-bit S-vector decoded from the b-vector

Table 1: System Inputs and Outputs



Back

Complete System

As shown in Figure 1, the system is comprised of several subsystems. Each of these subsystems will be described below in greater detail along with additional subsystems as shown in Figure 2. A detailed block diagram (Figure 2) will help clarify the following descriptions and Table 2 describes the subsystems in tabular format.
 

b-vector

The b-vector is the seven-bit vector input from the external source, which is stored in a seven-bit register. If the signal is correct, the vector will be decoded and output from the system as a four-bit information vector. If the signal is incorrect, the vector will be retransmitted by the source and restored in the seven-bit register.
 

H-matrix

The H-matrix is a three-by-seven matrix, which takes its input from three predetermined seven-bit error-checking vectors. The vectors are stored in three seven-bit registers. The data is then sent through three sets of seven tri-state buffers that select which signal is to be transmitted into the matrix multiplier circuitry using a controller.
 

Controller

The controller manages the output from the H-matrix. This circuitry is activated by a signal from the source and then allows one seven-bit vector at a time to be manipulated by the matrix multiplier circuit.
 

Matrix Multiplier Circuit

The matrix multiplier circuit takes its inputs from the H-matrix and the b-vector to form the new three-bit S-vector. The circuitry will perform the following function: H*b = S. The resulting S-vector will be sent to the error-checking subsystem for analysis.
 

Error Checking Circuit

This circuit detects if an error is present in the b-vector transmitted from the source. It receives the S-vector and, through analysis of the bits, outputs a signal to indicate when an error is present.
 

Decoder Circuitry

The decoder subsystem receives the seven-bit b-vector as input and decodes the signal by removing the three parity bits and outputting a four-bit information vector.
 

Back
 

Subsystem
Inputs
Outputs
Source
Signal indicating if error is detected
Seven-bit b-vector
b-vector
Seven bits from source and signal indicating if error is detected
Stored seven-bit vector
H-matrix
Error-checking vectors
Three seven-bit vectors
Controller
Activation signal from source
Select signal 
Matrix Multiplier Circuitry
Stored seven-bit signal from b-vector and three seven-bit vectors from H-matrix
Three-bit S-vector
Error-Checking Circuit
Three-bit S-vector from matrix
Signal indicating error or no error detected
Decoder Circuitry
Stored seven-bit b-vector
Four-bit decoded vector

Table 2: Subsystem Inputs and Outputs



Back

Listed below is information pertaining to the design thus far. Since the design will be fabricated as a CMOS chip, it will require CMOS voltage levels. These levels are listed below in Table 3. An equipment list then itemizes what will be needed to implement the design next semester. (All parts and equipment are presently available in lab except for the MOSIS fabricated chip which will be handled by the advisor, Dr. Vinod Prasad.) In Table 4, the preliminary time table for future work on the design is listed. Finally, a few relevant patents and references are listed below that have helped in the design and will be referred to in the future.
 
 

CMOS Voltage Levels
Input Voltage VIL (Logic ‘0’) from 0 - .5V VIH (Logic ‘1’) from 4.5 - 5V
Output Voltage VOL (Logic ‘0’ ) 0V VOH (Logic ‘1’) 5V

Table 3: Datasheet



Back

Equipment and Parts Needed

Fall Semester: LogicWorks design finished.
Spring Semester:

First two weeks

LogicWorks chips used in design are broken down into their basic gate level.
Next two weeks Gate level design is perfected and simplified if possible.
Next three weeks Each chip that was broken down in LogicWorks is individually designed and tested in VLSI using L-edit (ex. 4-bit counter, D-flip flop, demultiplexer, etc.)
Next two weeks The different chips designed in VLSI are put together step by step according to the subsystem in which they belong.
Final weeks The whole design is tested and debugged. Work on the oral presentation and project report will begin.
Note: If time is allotted, the circuit will be implemented onto an FPGA chip using VHDL and will be tested.

Table 4: Tentative Schedule



Patents

    5,487,075 - High-speed staged decoder/quantizer

    6,154,871 - Error detection and correction system for a stream of encoded data

    6,282,689 - Error correction chip for memory applications

    6,320,201 - Semiconductor reliability test chip

    6,329,831 - Method and apparatus for reliability testing of integrated circuit structures and devices
 
 

Back

References

    Mano, Morris M. and Charles R. Kime. Logic and Computer Design Fundamentals.
            New Jersey: Prentice Hall, Inc., 1997.

    Uyemura, John P. Physical Design of CMOS Integrated Circuits Using L-EDITTM.
            Boston: PWS Publishing Company. 1995.

    Wakerly, John F. Digital Design Principles & Practices. Third Edition Updated.
            New Jersey: Prentice-Hall, Inc., 2001.
 
 

Back to top