hamming_edac¶

Dependencies¶

Description¶

This package provides functions that perform single-bit error detection and correction using Hamming code. Encoded data is represented in the ecc_vector type with the data preserved in normal sequence using array indices from data’length-1 downto 0. The Hamming parity bits p are represented in the encoded array as negative indices from -1 downto -p. The parity bits are sequenced with the most significant on the left (-1) and the least significant on the right (-p). This arrangement provides for easy removal of the parity bits by slicing the data portion out of the encoded array. These functions have no upper limit in the size of data they can handle. For practical reasons, these functions should not be used with less than four data bits.

The layout of an ecc_vector is determined by its range. All objects of this type must use a descending range with a positive upper bound and a negative lower bound. Note that the conversion function to_ecc_vec() does not produce a result that meets this requirement so it should not be invoked directly as a parameter to a function expecting a proper ecc_vector.

Hamming ecc_vector layout:

                           MSb         LSb
[(data'length - 1) <-> 0] [-1 <-> -parity_size]
          data               Hamming parity

The output from hamming_encode() produces an ecc_vector with this layout. Depending on the hardware implementation it may be desirable to interleave the parity bits with the data to protect against certain failures that may go undetected when encoded data is distributed across multiple memory devices. Use hamming_interleave() to perform this reordering of bits.

Background¶

The Hamming code is developed by interleaving the parity bits and data together such that the parity bits occupy the powers of 2 in the array indices. This interleaved array is known as the message. In decoding, the parity bits form a vector that represents an unsigned integer indicating the position of any erroneous bit in the message. The non-error condition is reserved as an all zeroes coding of the parity bits. This means that for \(p\) parity bits, the message length \(m\) can’t be longer than \((2^p)-1\). The number of data bits \(k\) is \(m - p\). Any particular Hamming code is referred to using the nomenclature \((m, k)\) to identify the message and data sizes. Here are the maximum data sizes for the set of messages that are perfectly coded \((m = (2^p)-1)\):

(3,1) (7,4) (15,11) (31,26) (63,57) (127,120) …

Minimum message sizes for power of 2 data sizes:

(5,2) (7,4) (12,8) (21,16) (38,32) (71,64) …

When the data size \(k\) is a power of 2 greater than or equal to 4, the minimum message size \(m = \lceil{\log_{2}k}\rceil + 1 + k\). For other values of \(k\) greater than 4 this relation is a, possibly minimal, upper bound for the message size.

Synthesis¶

The XOR operations for the parity bits are iteratively generated and form long chains of gates. To achieve minimal delay you should ensure that your synthesizer rearranges these chains into minimal depth trees of XOR gates. The synthesized logic is purely combinational. In most cases registers should be added to remove glitches on the outputs.

Example usage¶

signal word, corrected_word : std_ulogic_vector(15 downto 0);
constant WORD_MSG_SIZE : positive := hamming_message_size(word'length);
signal hamming_word :
  ecc_vector(word'high downto -hamming_parity_size(WORD_MSG_SIZE));
...
hamming_word <= hamming_encode(word);
... <SEU or transmission error flips a bit>
corrected_word <= hamming_decode(hamming_word);
if hamming_has_error(hamming_word) then ... -- check for error

Note that hamming_decode() and hamming_has_error() will synthesize with some common logic. Use the alternate versions in conjunction with hamming_interleave() and hamming_parity() to conserve logic when both are used:

variable message : std_ulogic_vector(hamming_word'length downto 1);
variable syndrome : unsigned(-hamming_word'low downto 1);
...
message  := hamming_interleave(hamming_word);
syndrome := hamming_parity(message);
corrected_word <= hamming_decode(message, syndrome);
if hamming_has_error(syndrome) then ... -- check for error

Similary, it is possible to share logic between the encoder and decoder if they are co-located and not used simultaneously:

if encoding then
  txrx_data   := word;
  txrx_parity := (others => '0');
else -- decoding
  txrx_data   := get_data(received_word);
  txrx_parity := get_parity(received_word);
end if;
message        := hamming_interleave(txrx_data, txrx_parity);
parity_bits    := hamming_parity(message); -- also acts as the syndrome
hamming_word   <= hamming_encode(word, parity_bits);
corrected_word <= hamming_decode(message, parity_bits);

Types¶

hamming_edac.ecc_vector¶: Representation of a message with data and parity segments.

hamming_edac.ecc_range¶: Range information for a message.

Subprograms¶

hamming_edac.to_ecc_vec (Arg : std_ulogic_vector; Parity_size : natural := 0) → ecc_vector¶

Convert a plain vector into ecc_vector.

Parameters:	Arg (std_ulogic_vector) – Vector to convert Parity_size (natural) – Number of parity bits
Returns:	Arg vector reindexed with a negative parity segment.

hamming_edac.to_sulv (Arg : ecc_vector) → std_ulogic_vector¶

Convert an ecc_vector to a plain vector.

Parameters:	Arg (ecc_vector) – Vector to convert
Returns:	Vector reindexed with 0 as rightmost bit.

hamming_edac.get_data (Encoded_data : ecc_vector) → std_ulogic_vector¶

Extract data portion from encoded ecc_vector.

Parameters:	Encoded_data (ecc_vector) – Vector to convert
Returns:	Data portion of Encoded_data.

hamming_edac.get_parity (Encoded_data : ecc_vector) → unsigned¶

Extract parity portion from encoded ecc_vector.

Parameters:	Encoded_data (ecc_vector) – Vector to convert
Returns:	Parity portion of Encoded_data.

hamming_edac.hamming_message_size (Data_size : positive) → positive¶

Determine the size of a message (data interleaved with parity) given the size of data to be protected.

Parameters:	Data_size (positive) – Number of data bits
Returns:	Message size.

hamming_edac.hamming_parity_size (Message_size : positive) → positive¶

Determine the number of parity bits for a given message size.

Parameters:	Message_size (positive) – Number of bits in complete message
Returns:	Parity size.

hamming_edac.hamming_data_size (Message_size : positive) → positive¶

Determine the number of data bits for a given message size.

Parameters:	Message_size (positive) – Number of bits in complete message
Returns:	Data size.

hamming_edac.hamming_indices (Data_size : positive) → ecc_range¶

Return the left and right indices needed to declare an ecc_vector for the requested data size.

Parameters:	Data_size (positive) – Number of data bits
Returns:	Range with left and right.

hamming_edac.hamming_interleave (Data : std_ulogic_vector; Parity_bits : unsigned) → std_ulogic_vector¶

Combine separate data and parity bits into a message with interleaved parity.

Parameters:	Data (std_ulogic_vector) – Unencoded data Parity_bits (unsigned) – Parity
Returns:	Message with interleaved parity.

hamming_edac.hamming_interleave (Encoded_data : ecc_vector) → std_ulogic_vector¶

Reorder data and parity bits from an ecc_vector into a message with interleaved parity.

Parameters:	Encoded_data (ecc_vector) – Unencoded data and parity
Returns:	Message with interleaved parity.

hamming_edac.hamming_parity (Message : std_ulogic_vector) → unsigned¶

Generate Hamming parity bits from an interleaved message This is the core routine of the package that determines which bits of a message to XOR together. It is employed for both encoding and decoding When encoding, the message should have all zeroes interleaved for the parity bits. The result is the parity to be used by a decoder. When decoding, the previously generated parity bits are interleaved and the result is a syndrome that can be used for error detection and correction.

Parameters:	Message (std_ulogic_vector) – Interleaved message
Returns:	Parity or syndrome.

hamming_edac.hamming_encode (Data : std_ulogic_vector) → ecc_vector¶

Encode the supplied data into an ecc_vector using Hamming code for the parity. This version uses self contained logic.

Parameters:	Data (std_ulogic_vector) – Raw data
Returns:	Encoded data with parity.

hamming_edac.hamming_encode (Data : std_ulogic_vector; Parity_bits : unsigned) → ecc_vector¶

Encode the supplied data into an ecc_vector using Hamming code for the parity. This version depends on external logic to generate the parity bits.

Parameters:	Data (std_ulogic_vector) – Raw data Parity_bits (unsigned) – Number of parity bits
Returns:	Encoded data with parity.

hamming_edac.hamming_decode (Encoded_data : ecc_vector) → std_ulogic_vector¶

Decode an ecc_vector into the plain data bits, potentially correcting a single-bit error if a bit has flipped. This version uses self contained logic.

Parameters:	Encoded_data (ecc_vector) – Encoded (uninterleaved) message
Returns:	Decoded data.

hamming_edac.hamming_decode (Message : std_ulogic_vector; Syndrome : unsigned) → std_ulogic_vector¶

Decode an interleaved message into the plain data bits, potentially correcting a single-bit error if a bit has flipped. This version depends on external logic to interleave the message and generate a syndrome.

Parameters:	Message (std_ulogic_vector) – Interleaved message
Returns:	Decoded data.

hamming_edac.hamming_has_error (Encoded_data : ecc_vector) → boolean¶

Test for a single-bit error in an ecc_vector. Returns true for an error.

Parameters:	Encoded_data (ecc_vector) – Encoded (uninterleaved) message
Returns:	true if message has a parity error.

hamming_edac.hamming_has_error (Syndrome : unsigned) → boolean¶

Test for a single-bit error in an ecc_vector. Returns true for an error. This version depends on external logic to generate a syndrome.

Parameters:	Syndrome (unsigned) – Syndrome generated by hamming_parity()
Returns:	true if message has a parity error.