Hadamard Codes and C Implementation Using the Octave GNU Tool
1. Abbreviation
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 WalshHadamard 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:
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 selfcorrecting codes. If there is a set of code words with a Hamming distance: d = 2t +1. Then this code can correct terrors 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
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:
The matrix consists of 1 and 1:
The rows of the matrix form code words with Hamming distance n/2. The code words are orthogonal to each other:
Formula (13) can be interpreted in two ways:

If we consider the code word as the coordinates of a vector in ndimensional space, then formula (13) is the scalar product of two vectors. Thus all Hadamard code words are orthogonal vectors

Formula (13) can be interpreted as a cross correlation between two code words. Thus Hadamard matrix has code words uncorrelated with each other
Thus in the table of code words each message has its inversion (17). Now if we calculate the crosscorrelation between the received message (without errors) and the pattern table (16) we get:
Further the Hadamard codes will be understood as the extended version of the code (16).
Using Hadamard codes allow to fix:
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: n2t, 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:
Note: This formula is easily proven and you can do it yourself.
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^(51))=(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)
ReedMuller 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^(kr). This code describes many already known codes (see the [5]), for example:
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]:
Addition and subtraction operations with XOR are used for calculations in (25):
as well as multiplications and divisions with multiplication modulo 2 operation:
Thus we obtain a finite field or Galois field of binary codes of length n, which is denoted by:
where it is used Modular Arithmetic modulo 2.
Consider ReedMuller Code R(1.5), which corresponds to Hadamard Code (32,6,16) with a generating matrix G of size 6×32:
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:
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 nonstandard (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 ReedMuller 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)

Hadamard Code (32,6,16) has a Hamming Distance of 16, which allows to fix((161)/2) = 7 errors in the code word

If there are more than 7 errors in the code word of Hadamard (32,6,16), then the algorithm leads to incorrect corrections

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

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

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 CCode
% 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)