CryptologyA program for the WALSH transform |
|
The program reads from standard input and writes to standard output. The output was generated by the command line
wt < data.txt > result.txt
Input and output are in »natural order«: The bit string u1u2u3u4 is represented by the integer 8u1 + 4u2 + 2u3 + u4.
The input function must assume only integer values.
As an example consider the integer valued function that is the character form of the BOOLEan function f defined by
f(x1,x2,x3,x4) = x1x2+x3x4.The value table (or truth table) of f is
Binary vector x | Value f(x) |
---|---|
0000 | 0 |
0001 | 0 |
0010 | 0 |
0011 | 1 |
0100 | 0 |
0101 | 0 |
0111 | 1 |
1000 | 0 |
1001 | 0 |
1010 | 0 |
1011 | 1 |
1100 | 1 |
1101 | 1 |
1111 | 0 |
The character form (or polar form) of f is g(x) := cf(x1x2x3x4) = (-1)x1x2+x3x4. Therefore the input file for wt is the right column of the table
Binary vector x | Value g(x) |
---|---|
0000 | 1 |
0001 | 1 |
0010 | 1 |
0011 | -1 |
0100 | 1 |
0101 | 1 |
0110 | 1 |
0111 | -1 |
1000 | 1 |
1001 | 1 |
1010 | 1 |
1011 | -1 |
1100 | -1 |
1101 | -1 |
1110 | -1 |
1111 | 1 |
The output file essentially consists of the value table of the transformed function g^:
Binary vector u | Value g^(u) |
---|---|
0000 | 4 |
0001 | 4 |
0010 | 4 |
0011 | -4 |
0100 | 4 |
0101 | 4 |
0110 | 4 |
0111 | -4 |
1000 | 4 |
1001 | 4 |
1010 | 4 |
1011 | -4 |
1100 | -4 |
1101 | -4 |
1110 | -4 |
1111 | 4 |
In this example g^ = 4 g. This is a special feature of this special function: g is »self-dual«.