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
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.
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.
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
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.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Table 2: Subsystem Inputs and Outputs
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
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
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.