H_MessageList

Hadamard Codes and C Implementation Using the Octave GNU Tool

1. Abbreviation

HdC_formula1_2

HdC_formula3_6

HdC_formula7

2. Introduction

This article is a continuation of the article: “Hamming Codes and C Implementation Using the Octave GNU Tool”. Hamming codes, despite their elegance, can only fix a single error. This article discusses a more efficient Hadamard code (also called Walsh code or Walsh-Hadamard code).
Now I will repeat here from the previous article some important coding provisions that will be required in the following description.
It is necessary often to ensure reliable data transmission or storage in Digital Signal Processing applications. Data will be understood messages (code words) containing zeros (0) and ones (1), that is binary data. Additional parity bits create differences between the data (code words). To estimate the difference between the codes, Hamming introduced a code distance. For example, there are two messages:

HdC_formula8

These two code words differ in four positions (see italics). The number of differences between binary messages is called the Hamming code distance. A theorem is known that is used to create self-correcting codes. If there is a set of code words with a Hamming distance: d = 2t +1. Then this code can correct t-errors that occur during data transmission or storage. The proof of this theorem can be seen in [1]. For example, Hamming codes have a code distance of 3, which a single error is corrected, and extended Hamming codes have a code distance of 4, which a single error is corrected and a double error is detected.
Code words can be interpreted as vector coordinates and treated as a vector space.
Next we will use the following notation for the code: (n,k,d), where

HdC_formula8_1

3. Hadamard Code (32,6,16)

The easiest way to get the Hadamard code is to use Hadamard matrix. Octave and Matlab Tools have the hadamard(n) function. To get the Hadamard code, the hadamard(n) function is calculated:

HdC_formula9_10

The matrix consists of -1 and 1:

HdC_formula11_12

The rows of the matrix form code words with Hamming distance n/2. The code words are orthogonal to each other:

HdC_formula13_15

Formula (13) can be interpreted in two ways:
  1. If we consider the code word as the coordinates of a vector in n-dimensional space, then formula (13) is the scalar product of two vectors. Thus all Hadamard code words are orthogonal vectors
  2. Formula (13) can be interpreted as a cross correlation between two code words. Thus Hadamard matrix has code words uncorrelated with each other

HdC_formula16_17

Thus in the table of code words each message has its inversion (17). Now if we calculate the cross-correlation between the received message (without errors) and the pattern table (16) we get:

HdC_formula18_21

Further the Hadamard codes will be understood as the extended version of the code (16).
Using Hadamard codes allow to fix:

HdC_formula22

The correction algorithm is simple, the cross correlation between the received message and the pattern table is calculated. The message from the pattern table, which has the maximum value of cross correlation (18), is accepted. This algorithm works correctly if (22) is correct.
Note: If there are t errors in the code word, then the (20) takes the value: n-2t, and (19) loses orthogonality and takes the values: -2t … 2t
Instead of the numbers -1 / 1, it is more convenient to use the values 0 / 1, therefore the Hadamard matrix is replaced by: 1 => 0 and -1 => 1. Next the bits 0 / 1 of the code are combined into words for example: uint32. Thus an array of 2n numbers will be obtained, and the formula (18) will take the form:
HdC_formula23
Note: This formula is easily proven and you can do it yourself.
HdC_formula24
Let’s replace in (24): 1 => 0 and -1 => 1. Next combine the rows of the matrix (24) into the uint32 words. As a result we get a table of 64 code words:

/* Hadamard Code (2^5,5+1,2^(5-1))=(32,6,16): 64×32 bit words with 0/1 values */
const uint32 H_MessageList[64]=
{
0x00000000, 0x55555555, 0x33333333, 0x66666666, 0x0F0F0F0F,
0x5A5A5A5A, 0x3C3C3C3C, 0x69696969, 0x00FF00FF, 0x55AA55AA,
0x33CC33CC, 0x66996699, 0x0FF00FF0, 0x5AA55AA5, 0x3CC33CC3,
0x69966996, 0x0000FFFF, 0x5555AAAA, 0x3333CCCC, 0x66669999,
0x0F0FF0F0, 0x5A5AA5A5, 0x3C3CC3C3, 0x69699696, 0x00FFFF00,
0x55AAAA55, 0x33CCCC33, 0x66999966, 0x0FF0F00F, 0x5AA5A55A,
0x3CC3C33C, 0x69969669, 0xFFFFFFFF, 0xAAAAAAAA, 0xCCCCCCCC,
0x99999999, 0xF0F0F0F0, 0xA5A5A5A5, 0xC3C3C3C3, 0x96969696,
0xFF00FF00, 0xAA55AA55, 0xCC33CC33, 0x99669966, 0xF00FF00F,
0xA55AA55A, 0xC33CC33C, 0x96699669, 0xFFFF0000, 0xAAAA5555,
0xCCCC3333, 0x99996666, 0xF0F00F0F, 0xA5A55A5A, 0xC3C33C3C,
0x96966969, 0xFF0000FF, 0xAA5555AA, 0xCC3333CC, 0x99666699,
0xF00F0FF0, 0xA55A5AA5, 0xC33C3CC3, 0x96696996
};

Example:
Let the 3rd message from H_MessgeList be received: 0x33333333 then:
3th message: without mistake. Cross correlation with the H_MessageList patterns:
0 0 32 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
-32 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3th message: with 1 mistake. Cross correlation with the H_MessageList patterns:
2 2 30 -2 2 2 -2 -2 -2 -2 2 2 -2 -2 2 2 -2 -2 2 2 -2 -2 2 2 2 2 -2 -2 2
2 -2 -2 -2 -2 -30 2 -2 -2 2 2 2 2 -2 -2 2 2 -2 -2 2 2 -2 -2 2 2 -2 -2 -2 -2 2 2 -2 -2 2 2
3th message: with 2 mistakes. Cross correlation with the H_MessageList patterns:
0 0 28 -4 0 0 -4 -4 0 0 4 4 0 0 4 4 0 0 4 4 0 0 4 4 0 0 -4 -4 0 0 -4 –
4 0 0 -28 4 0 0 4 4 0 0 -4 -4 0 0 -4 -4 0 0 -4 -4 0 0 -4 -4 0 0 4 4 0 0 4 4
3th message: with 7 mistakes. Cross correlation with the H_MessageList patterns:
2 2 18 -14 -2 -2 -2 -2 -2 -2 -2 -2 2 2 2 2 2 2 10 10 -2 -2 6 6 -2 -2 6 6
2 2 -6 -6 -2 -2 -18 14 2 2 2 2 2 2 2 2 -2 -2 -2 -2 -2 -2 -10 -10 2 2 -6 -6 2 2 -6 -6 -2 -2 6 6
Note. Further it is impossible to receive the message correctly if the number of errors is more than 7!
3th message: with 8 mistakes. Cross correlation with the H_MessageList patterns:
0 0 16 -16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 8 0 0 8 8 0 0 8 8 0 0 -8 -8 0 0 -16 16 0 0
0 0 0 0 0 0 0 0 0 0 0 0 -8 -8 0 0 -8 -8 0 0 -8 -8 0 0 8 8 -8 0 0 -8 -8 0 0 -8 -8 0 0 8 8
3th message: with 9 mistakes. Cross correlation with the H_MessageList patterns:
2 2 14 -18 2 2 -2 -2 -2 -2 2 2 -2 -2 2 2 2 2 6 6 2 2 6 6 -2 -2 10 10 -2
-2 -6 -6 -2 -2 -14 18 -2 -2 2 2 2 2 -2 -2 2 2 -2 -2 -2 -2 -6 -6 -2 -2 -6 -6 2 2 -10 -10 2 2 6 6
See also the HadamardCode.m/c/h and you can read more in [2], [3]

4. Generator Matrix G of the Hadamard Code using the Reed–Muller Code R(1,k)

Reed-Muller codes are linear codes, which are denoted by R(r,k), where r is the order of the code with code word length 2^k and Hamming distance 2^(k-r). This code describes many already known codes (see the [5]), for example:

HdC_formula24_1

It is convenient to describe linear codes in matrix form using a generator matrix G of size (k)x(n) and information codes: u1,…,uk. See the [1], [2]:

HdC_formula25

Addition and subtraction operations with XOR are used for calculations in (25):

HdC_formula26

as well as multiplications and divisions with multiplication modulo 2 operation:
HdC_formula27
Thus we obtain a finite field or Galois field of binary codes of length n, which is denoted by:

HdC_formula27_1

where it is used Modular Arithmetic modulo 2.
Consider Reed-Muller Code R(1.5), which corresponds to Hadamard Code (32,6,16) with a generating matrix G of size 6×32:
HdC_formula28
The first row of the G matrix consists of ones. The rest of the matrix consists of five rows, the columns of which are increasing: 00000, 00001, 00010, 00011 … 11111. The message table is calculated using the formula:
HdC_formula29
The Hadamard code words are calculated with (29) by substituting the values (u1, u2, …, u6):
(0 0 0 0 0 0), (0 0 0 0 0 1), (0 0 0 0 1 0), …, (1 1 1 1 1 1). These calculations are performed in the HadamardCode.m
Notes:
  • The G generator matrix (28) has a non-standard (non systematic) form and it is difficult to extract the information bits u1,…, u6 from the Hadamard code. It is more convenient in this case to work with the message number
  • I prefer to generate a message table using the Hadamard matrices described in the previous chapter
  • The Reed-Muller decoder is built using a majority method, which is similar to the method that was shown in the previous section

5. Conclusions for Hadamard Code (32,6,16)

  1. Hadamard Code (32,6,16) has a Hamming Distance of 16, which allows to fix((16-1)/2) = 7 errors in the code word
  2. If there are more than 7 errors in the code word of Hadamard (32,6,16), then the algorithm leads to incorrect corrections
  3. It follows from the previous point that the use of Hadamard codes (32,6,16) is limited to 7 errors. If there is a high probability of more than 7 errors in the code word, then in the case the codes with a greater Hamming distance should be used and allowing the necessary number of errors to be corrected
  4. Often a message consisting of only zeros, as well as a message consisting of only ones, are excluded from the list of Hadamard Code messages. This is due to the fact that in cases of a reception failure, the system often mistakenly accepts a message consisting of only zeros or ones
  5. Hadamard Code (32,6,16) was used by NASA in 1971 to transmit photos from Mars (NASA Mariner 9 Program). It is noted in [1] that more effective codes have now been developed for this purpose.

6. Octave GNU file HadamardCode.m

The script generates and tests Hadamard Code: (32,6,16) и R(1,5)

% Comparing two Messages: Input and Pattern
% Input parameters:
% InMessage – input message
% PatternMessage – Hadamard pattern message list
% HadamardMessageLength – Hadamard message length in bits
% Output parameters:
% CompareValue – correlation value
function CompareValue = MessageCompare(InMessage, PatternMessage, HadamardMessageLength)

% Receiving the Hadamard code message
% Majority logic decoding
% Input parameters:
% InMessage – input message
% HadamardMessageList – Hadamard message list
% HadamardMessageLength – Hadamard message length in bits
% Output parameters:
% Majority – max compare value
% MessageNmb – number of the message in the HadamardMessageList
% OutputValues – compare results for all the HadamardMessageList
function [Majority MessageNmb OutputValues] = ReceivingHadamardMessage(InMessage,  HadamardMessageList, HadamardMessageLength)

% Hex Integer Table to File
% Support C-Code
% Input parameters:
% ParameterVector – data array
% FileNameString – output file name
function HexIntegerParamVector2file(ParameterVector, FileNameString)

7. C Language HadamardCode.c/h

Support the Hadamard Code: (32,6,16)

/*
Hamming Distance between code1 and code2
Input
uint32 code1
uint32 code2
Return
uint8 – Hamming Distance
*/
uint8 HammingDistance(uint32 code1, uint32 code2)

/*
Compare or correlate the code1 and code2
Input
uint32 code1
uint32 code2
Return
sint8 – correlation value
*/
sint8 MessageCompare(uint32 code1, uint32 code2)

/*
Receiving the Hadamard message
Input
uint32 code – input message
receiving_message_t* ptr_result – pointer on the receiving result
Return
void
*/
void ReceivingHadamardMessage(uint32 code, receiving_message_t* ptr_result)

8. Download the HadamardCode.m/c/h

You can download the files:
HadamardCode.m
HadamardCode.c/h
with the button:

9. Literature / References

[1] Richard E. Blahut “Theory and Practice of Error Control Codes“, Addison-Wesley, 1984
[2] W. Wesley Peterson, E. J. Weldon “Error-Correcting Codes”, Cambridge, Massachusetts, and London, England, 1972
[3] F. J. Mac Williams, N. J. A. Sloane “The Theory of Error-Correcting Codes”, Bell Laboratories, Murray Hill NJ 07974, 1977
[4] M. N. Arshinov, L. E. Sadovsky “Codes and Mathematics (stories about coding)“, Moscow, 1983
[5] Wikipedia: Reed-Muller Code