4 August 2018

LINK-11 CLEW, Hamming check matrix

The check of a Link-11 CLEW stream discussed in the end part of this post, can be speed up by using the Hamming check matrix for the H(30,24) coding, ie a 30-bit code word consisting of 24 bits for data + 6 bits for Hamming parity bits (termed EDAC in Link-11 literature). The check matrix is constructed as shown in MIL 188-203-1A #5.2.4.1 and here.

Code verification is carried out by comparing each line of code in turn with all rows of the check matrix, except the extra parity line (the overall parity bit): the vertical correspondences of the "1" locations in the code line and in the row #n of the check sub matrix are counted. If the matches are even then the correspondent location #n in the EDAC bits will be "1", otherwhise (ie matches are a odd number) will be "0" (odd parity).
 
  EDAC           data
110100 000001110101110001100010
010011 111001110010010001111011
110100 111100101110010110011111
100100 010111010000110110000110
010010 011010000000010100100111
110001 010001110110000010010000

     check sub-matrix           identity sub-matrix
111111111111100000000000 010000
111111000000011111110000 001000
110000111100011110001110 000100
001100110011011001101101 000010
101010101010110101011011 000001
111111111111111111111111 111111
Test the first line of code 000001110101110001100010

000001110101110001100010
111111111111100000000000 check matrix line #0
6 matches, EDAC bit #0 shall be 1

000001110101110001100010
111111000000011111110000 check matrix line #1
4 matches, EDAC bit #1 shall be 1

000001110101110001100010
110000111100011110001110 check matrix line #2
5 matches, EDAC bit #2 shall be 0

000001110101110001100010
001100110011011001101101 check matrix line #3
6 matches, EDAC bit #3 shall be 1

000001110101110001100010
101010101010110101011011 check matrix line #4   
5 matches, EDAC bit #4 shall be 0
EDAC bits 0-4: 11010

Test the second line of code 111001110010010001111011

111001110010010001111011
111111111111100000000000 check matrix line #0
7 matches, EDAC bit #0 shall be 0

111001110010010001111011
111111000000011111110000 check matrix line #1
8 matches, EDAC bit #1 shall be 1

111001110010010001111011
110000111100011110001110 check matrix line #2
7 matches, EDAC bit #2 shall be 0

111001110010010001111011
001100110011011001101101 check matrix line #3
9 matches, EDAC bit #3 shall be 0

111001110010010001111011
101010101010110101011011 check matrix line #4   
10 matches, EDAC bit #4 shall be 1

EDAC bits 0-4: 01001
The verification of the remaining combinations confirms the use of the same method of checking (if you want, you can check it yourself).

If only one error is detected, it is corrected and sent to the computer. The computer is also advised that the word contained an error and that it is corrected. If two errors are detected the Hamming decoding can only determine that errors exist but cannot determine which bits are in error.