CMOS Gate Array Design Exercise 1998

Design Specification

Hamming Encoder/Decoder

Introduction

This year's exercise is to design an encoder or a decoder for an (8,4) Hamming error correcting code.

(8,4) Hamming Error Correction Code

Simple parity checks can be used to detect errors in a communications link. When an error is discovered the data is discarded and must be re-transmitted.

In certain systems it is desired not only to detect the error but also to correct it without re-transmission. There are a number of different error correcting codes which could be used, but we shall only consider a simple block code which is used by Teletext.

The code has four data bits and four parity bits and is capable of correcting a single error, and detecting certain combinations of multiple errors.

Coding the data

Before transmission, the four bit data word is converted to an eight bit code word by interleaving it with four parity bits.

The four original data bits are b₇(=d₃), b₅(=d₂), b₃(=d₁) and b₁(=d₀).

The four parity bits are b₆, b₄, b₂ and b₀.

     Data Word         Code Word
      d     d      b                b
       3     0      7                0
        0000         0 0 0 1 0 1 0 1
        0001         0 0 0 0 0 0 1 0
        0010         0 1 0 0 1 0 0 1
        0011         0 1 0 1 1 1 1 0
        0100         0 1 1 0 0 1 0 0
        0101         0 1 1 1 0 0 1 1
        0110         0 0 1 1 1 0 0 0
        0111         0 0 1 0 1 1 1 1
        1000         1 1 0 1 0 0 0 0
        1001         1 1 0 0 0 1 1 1
        1010         1 0 0 0 1 1 0 0
        1011         1 0 0 1 1 0 1 1
        1100         1 0 1 0 0 0 0 1
        1101         1 0 1 1 0 1 1 0
        1110         1 1 1 1 1 1 0 1
        1111         1 1 1 0 1 0 1 0

The code word is then transmitted bit serially starting with bit b₀.

Decoding the data

Detection and correction of errors

When the potentially corrupted data is received, the Syndrome {A,B,C,D} is calculated using the following rules: (n.b. `+' here is modulo 2 addition i.e. exclusive-or)

A = b₇ + b₅ + b₁ + b₀

B = b₇ + b₃ + b₂ + b₁

C = b₅ + b₄ + b₃ + b₁

D = b₇ + b₆ + b₅ + b₄ + b₃ + b₂ + b₁ + b₀

• If there are no errors then all the Syndrome bits will be `1'

• If there is only one error then D will be `0' and it is possible to determine which bit is in error by examining the other syndrome bits. If a data bit is in error it can be corrected.

• If there are two errors then D will be `1' while one or more of the other syndrome bits are `0' indicating multiple errors - no correction is possible.

• If there are three or more errors then the code will fail and an incorrect data word may be decoded without the flagging of an error.

The table below shows how the syndrome can be interpreted.

Syndrome	Inference
ABCD
0000	Error in b1
1000	Error in b3
0100	Error in b5
1100	Error in b4
0010	Error in b7
1010	Error in b2
0110	Error in b0
1110	Error in b6
0001	Multiple errors: cannot correct.
1001	Multiple errors: cannot correct.
0101	Multiple errors: cannot correct.
1101	Multiple errors: cannot correct.
0011	Multiple errors: cannot correct.
1011	Multiple errors: cannot correct.
0111	Multiple errors: cannot correct.
1111	No Error

The system when fully completed will be connected as shown:

Detailed Specification

As mentioned above, you must implement either a Hamming encoder or a Hamming decoder on the ULA. Once the designs have been fabricated, a full system will be built using an encoder from one team and a decoder from another team.

General Information

• You can only use the gates which are available on the ULA:
  • AND_2 OR_2 XOR_2 XNOR_2 INV NAND_4 NAND_3 NAND_2 NOR_3 NOR_2
  • D_TYPE macro

• Synchronous Design:

  All designs must be fully synchronous. Major penalties will be incurred by teams who adopt asynchronous or quasi-synchronous design styles; as well as losing marks you will probably find that your design doesn't work.

  A fully synchronous design contains no spurious state elements; no RS flip-flops, no transparent latches and no feedback paths within combinational logic blocks. The only state elements will be the the edge triggered D-types as supplied in the ULA library.

• Common Inputs

  • CLOCK

    A single clock signal with an active rising edge is common to all D-types. You should not attempt to connect this signal to any gate input or output which is not labelled CLOCK.

  • nRESET

    A single active-low asynchronous reset signal is common to all D-types, this input is used for initialization only. You should not attempt to connect this signal to any gate input or output which is not labelled nRESET.

Encoder Specification

• Inputs
  • START

    The START input will go high for one cycle when the data is available on the data inputs.

    The encoder should not accept two START pulses within any eight cycles as this will corrupt the output stream.

  • D3 D2 D1 D0

    Parallel data inputs. You may assume that these will remain stable for eight clock cycles after the start signal goes high.

• Outputs
  • DATA

    Serial data output. Eight bit code words are transmitted bit serially starting with bit b₀. When no code word is being transmitted, this output should return to zero.

  • STROBE

    The STROBE output must go high when bit b₀ is output. It is low at all other times.

Decoder Specification

• Inputs
  • DATA

    Serial data input.

  • STROBE

    The STROBE input will go high for one cycle when b₀ is available on the serial input.

• Outputs
  • READY

    The READY output must go high for one cycle when the data becomes ready.

  • D3 D2 D1 D0

    Parallel data output. The data need only be valid for the single cycle that the READY signal is high.

  • ERROR

    Each design should also have an ERROR output which indicates whether an error has been detected during the receipt of data. Such an error is signalled while READY is high and will remain at zero at all other times.

Encoder or Decoder?

The choice of a circuit for implementation will be one of your most important design decisions for this exercise. In the initial stages you may like to produce outline designs for both an encoder and a decoder. It is certainly possible that one or more of your initial designs will need more than the 67 available gate sites.

In choosing between designs, the key points to consider are:

1. You will get more marks for a simple functional design than for an ambitious design that doesn't quite work.
2. As you use more of the ULA the wiring becomes harder. Thus a design which uses all 67 available gate sites may take twice as long to route as one that uses only 57.

A good decoder design will be slightly larger than a good encoder design.

A hint for teams who are struggling: A simple implementation of the encoder circuit which doesn't meet the specification for rejecting multiple START signals within eight clock cycles will fit easily onto the ULA and will receive a reasonable mark (if designed and implemented well).

Note that if you chose to relax the specification such as described above you must document this in both your interim and your final reports.