Copyright © 2001 by Neal R. Wagner. All rights reserved.
NOTE: This site is obsolete. See book draft (in PDF):
Here is the Java simulation program in three files. The program uses the blocksize (variable N in file Shannon.java, accessible as a command line argument). The program calculates 2**N as the size of the code table (variable expN in file Shannon.java). The length of each codeword in bytes is also a variable (CWS in file Shannon.java) accessible as a command line argument. Thus the number of bits in each codeword is 8*CWS.
The main data structure is the coding table: expN entries each of size CWS bytes. Each entry is the class Word, and the table itself is of class Table. This coding table is allocated inside Table.java, and each entry is allocated inside Word.java and filled with random bits.
The simulation is repeated simSize many times (another command line argument inside Shannon.java). At each iteration, a random index in the coding table is chosen (length N bits), and the corresponding codeword (length CWS bytes) is fetched from the table. The codeword is "perturbed" by reversing each bit with probability 1 - p = 0.25, where p is a variable inside Shannon.java. The table is then checked for the closest match to this new perturbed word. Here "closest" means to check each entry to see the number of bit positions in which it differs from the perturbed word. The program focuses on the word or words in the table that differ from the perturbed word in the smallest number of bit positions. If there is more than 1 "closest match", this is regarded as an error, as is the case in which the closest match is a word different from the original unperturbed word. (In case of more than one closest match, one could choose a word at random, but this program does not do that.) The error rate is simply the percent of errors compared with all trials.
The program uses a reasonably clever and efficient method for comparing codewords (as bit strings). They are compared byte-by-byte. To compare two bytes, say b1 and b1, in function countDiffs inside file Table.java, the function first calculates b = b1 ^ b2 (the bit-wise exclusive-or). A 1 bit in b represents a difference in the two byte values, so one needs only to count the number of 1s in the byte b. This is done with a table lookup in the array c, declared in Word.java, but used in Table.java. The variable b ranges from -128 to 127 inclusive, so it is necessary to access c[b+128] and to create c to give the correct answers when used in this way. The array of Strings s (inside Word.java) gives the bit representation of each value of b, but this was only used for debugging.
// Word.java: an array of CWS (codeword size) bytes
import java.util.Random;
public class Word {
public static String[] s = { // table only needed for debugging
// values are from -128 to 127, 2s comp representation
"10000000","10000001","10000010","10000011","10000100","10000101","10000110","10000111",
"10001000","10001001","10001010","10001011","10001100","10001101","10001110","10001111",
"10010000","10010001","10010010","10010011","10010100","10010101","10010110","10010111",
"10011000","10011001","10011010","10011011","10011100","10011101","10011110","10011111",
"10100000","10100001","10100010","10100011","10100100","10100101","10100110","10100111",
"10101000","10101001","10101010","10101011","10101100","10101101","10101110","10101111",
"10110000","10110001","10110010","10110011","10110100","10110101","10110110","10110111",
"10111000","10111001","10111010","10111011","10111100","10111101","10111110","10111111",
"11000000","11000001","11000010","11000011","11000100","11000101","11000110","11000111",
"11001000","11001001","11001010","11001011","11001100","11001101","11001110","11001111",
"11010000","11010001","11010010","11010011","11010100","11010101","11010110","11010111",
"11011000","11011001","11011010","11011011","11011100","11011101","11011110","11011111",
"11100000","11100001","11100010","11100011","11100100","11100101","11100110","11100111",
"11101000","11101001","11101010","11101011","11101100","11101101","11101110","11101111",
"11110000","11110001","11110010","11110011","11110100","11110101","11110110","11110111",
"11111000","11111001","11111010","11111011","11111100","11111101","11111110","11111111",
"00000000","00000001","00000010","00000011","00000100","00000101","00000110","00000111",
"00001000","00001001","00001010","00001011","00001100","00001101","00001110","00001111",
"00010000","00010001","00010010","00010011","00010100","00010101","00010110","00010111",
"00011000","00011001","00011010","00011011","00011100","00011101","00011110","00011111",
"00100000","00100001","00100010","00100011","00100100","00100101","00100110","00100111",
"00101000","00101001","00101010","00101011","00101100","00101101","00101110","00101111",
"00110000","00110001","00110010","00110011","00110100","00110101","00110110","00110111",
"00111000","00111001","00111010","00111011","00111100","00111101","00111110","00111111",
"01000000","01000001","01000010","01000011","01000100","01000101","01000110","01000111",
"01001000","01001001","01001010","01001011","01001100","01001101","01001110","01001111",
"01010000","01010001","01010010","01010011","01010100","01010101","01010110","01010111",
"01011000","01011001","01011010","01011011","01011100","01011101","01011110","01011111",
"01100000","01100001","01100010","01100011","01100100","01100101","01100110","01100111",
"01101000","01101001","01101010","01101011","01101100","01101101","01101110","01101111",
"01110000","01110001","01110010","01110011","01110100","01110101","01110110","01110111",
"01111000","01111001","01111010","01111011","01111100","01111101","01111110","01111111"};
public static int[] c = { // num of 1 bits in 2s comp byte val (use value+128)
// used in class Table
1,2,2,3,2,3,3,4, 2,3,3,4,3,4,4,5, 2,3,3,4,3,4,4,5, 3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5, 3,4,4,5,4,5,5,6, 3,4,4,5,4,5,5,6, 4,5,5,6,5,6,6,7,
2,3,3,4,3,4,4,5, 3,4,4,5,4,5,5,6, 3,4,4,5,4,5,5,6, 4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6, 4,5,5,6,5,6,6,7, 4,5,5,6,5,6,6,7, 5,6,6,7,6,7,7,8,
0,1,1,2,1,2,2,3, 1,2,2,3,2,3,3,4, 1,2,2,3,2,3,3,4, 2,3,3,4,3,4,4,5,
1,2,2,3,2,3,3,4, 2,3,3,4,3,4,4,5, 2,3,3,4,3,4,4,5, 3,4,4,5,4,5,5,6,
1,2,2,3,2,3,3,4, 2,3,3,4,3,4,4,5, 2,3,3,4,3,4,4,5, 3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5, 3,4,4,5,4,5,5,6, 3,4,4,5,4,5,5,6, 4,5,5,6,5,6,6,7};
public byte[] w; // the only data field in this class
// Word: construct and fill bytes with random values
public Word(Random ranNumGen) {
w = new byte[Shannon.CWS]; // allocate CWS bytes
for (int j = 0; j < Shannon.CWS; j++)
w[j] = (byte)(256*ranNumGen.nextDouble() - 128);
}
// Word: construct and copy input Word u into new class
public Word(Random ranNumGen, Word u) {
w = new byte[Shannon.CWS];
for (int j = 0; j < Shannon.CWS; j++)
w[j] = u.w[j];
}
// printWord: used for debugging only
public void printWord() {
for(int i = 0; i < Shannon.CWS; i++)
System.out.print(s[w[i]+128] + " ");
System.out.println();
}
}
//Table.java: the code table for Shannon's random code
import java.util.Random;
public class Table {
public Word[] t; // the only data field in this class
// Table: constructor. Allocate expN = 2**N random words
public Table(Random ranNumGen) {
t = new Word[Shannon.expN];
for (int i = 0; i < Shannon.expN; i++)
t[i] = new Word(ranNumGen);
}
// search: search Table t for an input word w
public int search (Word w) {
int comp;
int minComp = Shannon.CWS*8 + 1;
int minCompCount = -100000000;
int index = -200000000;
for (int i = 0; i < Shannon.expN; i++) {
comp = compare(t[i], w); // count bits that differ
if (comp == minComp) // an old minimum
minCompCount++;
if (comp < minComp) { // a new minimum
// System.out.println(" Search: " + comp + ", Index: " + i);
index = i;
minComp = comp;
minCompCount = 1;
}
}
if (minCompCount == 1) return index; // unique minimum
else return -minCompCount; // several different minimums
}
// compare: return count of differences of bits of two input words
private int compare(Word u, Word v) {
int diffs = 0;
for (int i = 0; i < Shannon.CWS; i++)
diffs += countDiffs(u.w[i], v.w[i]);
return diffs;
}
// countDiffs: return count of differences of bits of two input bytes
private int countDiffs(byte b1, byte b2) {
byte b = (byte)(b1^b2); // xor gives 1 where bytes differ
return Word.c[b+128]; // table lookup gives number of 1 bits
}
// getWord: fetch a word at a given index, as part of simulation
public Word getWord(int index) {
return t[index];
}
// printTable: print the whole table, debug only
public void printTable() {
for (int i = 0; i < Shannon.expN; i++) {
System.out.print("Entry " + i + ": ");
t[i].printWord();
}
}
}
// Shannon.java: a simulation of Shannon's random coding
import java.util.Random; // use fancy rng during debugging to allow reproducability
public class Shannon {
public static final double P = 0.75; // prob of no error in trans a bit
public static int N; // blocksize, from command line
public static int expN; // = 2**N, table size, calculated from N
public static final double C = capacity(P);
public static int CWS; // the codeword size in bytes, from command line
private static Random ranNumGen = new Random(); // init different each time
public static double log2(double d) { // log2 not directly avail in Java
return Math.log(d)/Math.log(2.0);
}
public static double capacity(double p) { // channel capacity from p
if (p == 0 || p == 1) return 1;
return 1 + p*log2(p) + (1 - p)*log2(1 - p);
}
public static int randInt(int i) { // random int, between 0 and i-1 inclusive
return (int)(ranNumGen.nextDouble()*i);
}
// perturb: alter bits of an input word, each bit flipped with prob 1-P
public static Word perturb(Word v) {
Word u = new Word(ranNumGen, v);
int[] mask = {1, 2, 4, 8, 16, 32, 64, -128};
for (int i = 0; i < Shannon.CWS; i++)
for (int j = 0; j < 8; j++)
if (ranNumGen.nextDouble() > Shannon.P) {
u.w[i] = (byte)(mask[j]^u.w[i]);
// System.out.print("i:" + i + ", j:" + j + ";"); u.printWord();
}
return u;
}
public static void main(String[] args) {
int simSize = Integer.parseInt(args[0]); // the number of trials
N = Integer.parseInt(args[1]); // the block size
CWS = Integer.parseInt(args[2]); // the codeword size
expN = 1;
for (int i = 0; i < N; i++)
expN = expN*2; // expN = 2**N, the table size in Table.java
System.out.println("simSize: " + simSize + ", Blocksize: " + Shannon.N +
", Codeword size (bytes): " + Shannon.CWS +
", expN: " + Shannon.expN);
// count matches and two kinds of mismatches
int numMatch = 0, numNonMatch = 0, numMultiMatch = 0;
Table tab = new Table(ranNumGen); // the coding table
// tab.printTable();
for (int k = 0; k < simSize; k++) {
int ind = randInt(Shannon.expN); // ind is index of random code word
Word w = tab.getWord(ind); // w is the random code word
// System.out.print("Index: " + ind + "."); w.printWord();
Word u = perturb(w); // u is w with random noise added
// System.out.print("Perturbed word: "); u.printWord();
int ind2 = tab.search(u); // fetch closest match to perturbed code word
if (ind2 == ind) numMatch++;// System.out.println(" Matched");
else if (ind2 >= 0) { // matched the wrong code word, not one sent
numNonMatch++;
}
else if (ind2 < 0) numMultiMatch++; // multiple matches
if (k%500 == 499) {
System.out.print("Error Rate: " +
(k+1 - numMatch)/(double)(k+1));
System.out.println(", Match: " + numMatch +
", Non-Match: " + numNonMatch +
", Multiples: " + numMultiMatch);
}
} // for
System.out.print("Error Rate: " +
(simSize - numMatch)/(double)simSize);
System.out.println(", Match: " + numMatch +
", Non-Match: " + numNonMatch +
", Multiples: " + numMultiMatch);
}
}