TD 6, Error correcting codes – The Nordstrom-Robinson code

Introduction to Information Theory

February 10, 2023

The Nordstrom-Robinson code is a block code of length 16 containing 256 codewords. The list of its codewords is given here. It allows to encode 8 bits. It is therefore a code of rate 8/16=1/2.
Beware, today we will really work at the bit level (for instance the codewords will be represented by integers whose bit representation corresponds to the codewords).

1 Minimum Distance

The minimum distance is 6 (this is better than any linear code with the same parameters).

Write a program that calculates the distance enumerator of the code, that is for any distance w between 0 and 16, the number of pairs of codewords at Hamming distance w from each other.

2 Maximum Likelihood Decoder

Write an encoder, a binary symmetric channel simulator and a maximum likelihood decoder. This algorithms returns the closest codeword (with respect to the Hamming metric). This closest codeword might not be unique. Check your programs on the file hamlet.txt. Example:

  java Coder hamlet.txt >hamlet.code
  java Canal hamlet.code 0.01 > hamlet.canal 
  java Decoder hamlet.canal > hamlet.decode
  java Distance hamlet.decode hamlet.txt

Check your program for crossover probabilities in the range between 10⁻² and 10⁻⁴.

3 Bounded Distance Decoder

5 This code is of minimum distance 6, therefore it can correct 2 errors. Modify your decoder so that it corrects any error pattern of weight 1 and 2, but does not perform any correction otherwise (by returning for instance '*' when more than 2 errors are detected).

Check your decoder by printing the number of errors after decoding and the number of '*'.
Your test may look like

  seth $ java DecoderB hamlet.canal  hamlet.txt > hamlet.decodeB
  n_star= 88
  dist= 2

Appendix A: On the read() method

Recall that the method read() returns an int, which is in fact a byte between 0 and 255, and -1 for the end of the file. To obtain a word of length 16, two read()'s are necessary and they are concatenated in a single int (or short).

Appendix B : bit by bit operations on a byte/short/int

bit by bit addition modulo 2 (XOR) : x ^ y
bit by bit multiplication modulo 2 (and) : x & y
For example (x & 0xFF) sets to 0 all the bits of x with the exception of the 8 least significant ones (equivalent to (x % 256)).
Multiplication by a power of 2 (left shift of the binary representation ) : (x << i)
Division by a power of (right shift of the binary representation) : (x >> i)
Java constants in hexadecimal : they start with 0x the symbols from A to F range from 10 to 15. For instance 0x0137 is equal to 311 (1 0011 0111 in base 2) or 0x02E6 is equal to 742 (10 1110 0110 in base 2).
To compute the Hamming weight you can use the method Integer.bitCount(int) .