Crypto Type

I was using IF, so I leaving this (comment)
Error-Correcting Codes
After text has been compressed, and even more so after it has been encrypted, the resulting output is random in appearance. This makes it easy to make mistakes in handling it, and hard to see errors if they are introduced through electrical noise on a communications link or any similar cause.
Thus, even if redundancy is removed as far as is possible before encryption by means of data compression, after encryption is complete, it becomes desirable to put redundancy back in, to give resistance to errors.
There are mathematical techniques, given an arbitrary text, to add more symbols to it in a way that gives resistance to a specific number of errors. Since they depend only on the input text, if the ciphertext is used as input, this kind of added redundancy does not help the cryptanalyst, except by giving both him and the legitimate recipient a copy of the ciphertext that is more likely to be accurate.
 The row of the top square, and the column of the square on the lower right, which contain digraphs beginning with *, are omitted, since those are unused if codewords from a 26-letter alphabet are wanted.

Valid codewords consist of two letters from the top, a letter from the lower left, and two letters on the lower right, such that the single letter shares the same column as the pair of letters from the top and the same row as the pair of letters from the lower right. The use of an extra dummy letter * is required to avoid codewords differing only by a swap of two adjacent letters, because there are an even number of letters in the alphabet. The middle square can start with any letter; here it is started with M to indicate that this feature can be used to produce codewords different from those in someone else's code.
Thus, the first few codewords in alphabetical order that can be generated from the square above are:
AAAAM AAABN AAACO AAADP AAAEQ AAAFR AAAGS AAAHT
AAAIU AAAJV AAAKW AAALX AAAMY AAANZ AAAPA AAAQB
AAARC AAASD AAATE AAAUF AAAVG AAAWH AAAXI AAAYJ
AAAZK
AABAL AABBM AABCN AABDO ...
AACAK AACBL AACCM AACDN ...
AADAJ AADBK AADCL AADDM
The underlying principle of the diagram above is simply, for a five-character codeword that can be represented as abcde, to keep a-b+c-d+e a constant value, modulo 27.
The fact that this type of coding only protects against two characters being swapped when the alphabet has an odd number of letters in it is also the reason why the check digit for ISBN numbers (okay, that stands for International Standard Book Number, so I was redundant) can also be an X in addition to a digit from 0 to 9.
For example, given a string of bits, a single bit which contains the parity of that string of bits can be appended to it. In that case, if the result is transmitted, and exactly one bit is in error in what is recieved, the parity will be wrong, and the fact that an error has taken place will be detected.
Another simple example would be to transmit one's message three times. For every group of three corresponding bits from the three copies of the message, if exactly one error takes place in communications, that error can be corrected, because of the three recieved copies of that bit, two will be correct, and only one will be wrong.
Repeating a bit an odd number of times is a trivial example of a perfect code; a parity bit, and repetition an even number of times, are both examples of extended codes based on perfect codes, where an extended code is formed from any code by adding a parity bit, because having no error-checking bits added to a block is also a trivial example of a perfect code.
If we confine ourselves to the even parity form of a parity bit, both these codes can be represented by matrices:
A parity bit:
1 0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0 1
0 0 1 0 0 0 0 0 1
0 0 0 1 0 0 0 0 1
0 0 0 0 1 0 0 0 1
0 0 0 0 0 1 0 0 1
0 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 1 1
Triple repetition:
1 1 1
In general, matrix multiplication works like this: introduce the numbers which are the elements of the vector being multiplied from the left, starting with the first one on the top; for each bit in that row, calculate the product of the number introduced from the side with the number in the matrix; then, after all the products have been calculated, total them down the columns to obtain the output.
For error-correcting codes illustrated by matrices, it is the bits of the message that are introduced from the left. Then, an AND is performed (rather than a multiplication) between them and the bits of the matrix, and the results are accumulated by an XOR going down the columns (rather than addition).
Illustrating this in the case of a parity bit applied to a nybble:
    1   0   0   0   1

1 -->  1   0   0   0   1
    0   1   0   0   1

0 -->  0   0   0   0   0
    0   0   1   0   1

1 -->  0   0   1   0   1
    0   0   0   1   1

1 -->  0   0   0   1   1
-------------------
1   0   1   1   1
As this is a code applied to a binary signal, all arithmetic is done modulo 2 (hence, 1+1+1 = 1 instead of 3).
Just using parity bits can allow correcting errors. One way to do this is to have both a parity bit for each byte of data, and a parity byte that results from the XOR of all the data bytes. If there is one error, the byte it is in is indicated by the parity bit for that byte, and the bit it is in is indicated by which byte of the final parity byte shows the wrong parity.
A simple way to obtain row and column parity for a sequence of characters on a computer would be to add three parity characters to a line of 49 7-bit characters on this basis:
Start with three seven-bit accumulators, initialized to zero.
With each character read, modify the three accumulators as follows:
XOR the character to the first accumulator, and rotate it right one bit.
XOR the character to the second accumulator, and rotate it left one bit.
XOR the character to the third accumulator, and after every seven characters, rotate it right one bit.
This would allow one single-bit error in a line to be found and therfore corrected, as follows:
33333X3------------------------------------ ==?
----2-133333----2-1----2-1----2-1----2-1----2-1 ===
1--2---1--2---333331--2---1--2---1--2---1--2--- ?==
-12-----12-----12----33333-12-----12-----12---- ===
-21-----21-----21-----21----33333-21-----21---- ===
2--1---2--1---2--1---2--1---2--1---333332--1--- =?=
----1-2----1-2----1------1-2----1-2----1-233333 ===
The X is at the only point where the three lines of bits marked by 1, 2, and 3 all coincide. Note that the asterisks mark points where two of them cross. Assuming the shifts after a byte is XORed in even take place after the last byte, the question marks indicate where the three parity characters would show the wrong parity if there was an error at the point marked by the X.
It is easier to do this for 7-bit characters because 7 is an odd number, but it can also be done for 8-bit bytes, simply by rotating only one accumulator by one bit for each byte, and not rotating one accumulator at all, as follows:
33313333---1-------1-------1-------1-------1-------1-------1---- ==?
----1---3333333----1-------1-------1-------1-------1-------1--- ===
22222222222222***X22222222222222222222222222222222222 =?=
------1-------1-------1-3333333------1-------1-------1-------1- ===
-------1-------1-------1-------13333333-------1-------1-------1 ===
1-------1-------1-------1-------1-------33333331-------1------- ?==
-1-------1-------1-------1-------1-------1------3333333-1------ ===
--1-------1-------1-------1-------1-------1-------1-----33*33333 ===
However, approaches based only on using parity bits are unsophisticated, and more efficient ways of correcting and detecting multiple errors can be found if more sophisticated codes are used.
Another class of error-correcting codes are called Hamming codes. No longer trivial, these codes are also perfect, which means they add exactly enough redundancy to a group of input bits to detect and correct a certain number of errors.
Note that this perfection applies to one particular situation, where errors occur randomly among bits. Where there is a tendency for bits close together in a message to be in error together, this being called a burst error, other strategies are needed. One common way of dealing with this is simply to apply conventional error-correcting codes to widely-separated bits at equal intervals in a message. This, or the strategy of applying the error-correcting code first, and then spreading out the bits of each output group, is called interleaving.
The Hamming Codes
In a Hamming code, after the group of bits being encoded, the extra parity bits are formed by allocating every combination of those bits with two or more of them equal to 1 to each bit position in the input. Hence, changing one bit in the input always changes at least three bits in the word with error-correction added. Since no two rows in the error-checking part of the matrix are identical, changing two bits in the input still results in a three-bit change at least; thus, the number of bits difference (or the Hamming distance) between possible outputs (valid codewords) is a minimum of three.
A parity bit can be added to a Hamming code; the result is another perfect code, this time with a four-bit change resulting from any change in the input.
The Hamming distance between valid codewords tells us how much error-checking we have. If there is no error-checking added, each different input still gives a different output, for a distance of 1. If the distance is 2, one error can be detected, as is the case for the code that just adds one parity bit. If the distance is 3, as for repeating a bit three times, or the basic Hamming code without a parity bit added, one error can be corrected.
The error-correcting capabilities of an error-correcting code are given by the Hamming distance between codewords, but it is possible to choose how to make use of them. For example, if we repeat every bit three times, we can either choose to accept 011 as standing for 1, hence correcting one error when it occurs, but being fooled if two errors happen, or we can choose to discard it, accepting only 000 and 111. Thus, a Hamming distance of 3 can be used either to correct one error, or to detect two errors. A distance of 4, such as obtained by a Hamming code with a parity bit, or by repeating a bit four times, allows correcting one error and detecting two errors, or detecting up to three errors.
Some Hamming codes are:
1 0 0 0 0 1 1
0 1 0 0 1 0 1
0 0 1 0 1 1 0
0 0 0 1 1 1 1
1 0 0 0 0 0 0 0 0 0 0 0 0 1 1
0 1 0 0 0 0 0 0 0 0 0 0 1 0 1
0 0 1 0 0 0 0 0 0 0 0 0 1 1 0
0 0 0 1 0 0 0 0 0 0 0 1 0 0 1
0 0 0 0 1 0 0 0 0 0 0 1 0 1 0
0 0 0 0 0 1 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 1 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 1 0 0 0 1 0 1 1
0 0 0 0 0 0 0 0 1 0 0 1 1 0 1
0 0 0 0 0 0 0 0 0 1 0 1 1 1 0
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
1 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 1 1
0 1 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 1 0 1
0 0 1 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 1 1 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 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 1 1 1 1 1 1
Since a Hamming code, as shown, can only correct one error, decoding is simple:
Take the data portion of the recieved codeword (the portion that should just contain the unmodified input data), and place it through the Hamming code again. If there is a perfect match between the error-checking part of the recieved block and the error-checking part of the one now generated, or if there is no more than one bit difference, the data as recieved is assumed to be correct.
If there are two or more bits of difference, find the row in the matrix where those bits are 1 bits in the error checking part. The data bit which is passed through by a 1 on the diagonal in the data part of the matrix is the one in error.
This, of course, assumes that the transmitted block actually was subjected to no more than one error. When a parity bit is added to the Hamming code, decoding is modified slightly:
If parity is correct, decode the first part of the block, but accept the result only if no errors are found. (In this case, the block is assumed to have been recieved correctly.)
If parity is wrong, decode the first part of the block, and accept the result if either no errors are found (here, the error is assumed to be in the parity bit itself), or if one error is found (and therefore corrected).
These are just one particular form for each of the three Hamming codes shown. Rearranging the rows or columns, or certain other modifications, will not change the ability of the code to be used to detect or correct errors. Replacing one row of the matrix by the XOR of itself and another row is allowed, because that will result in the matrix generating exactly the same set of codewords, but they will be generated in some cases for different inputs.
As we have noted, the minimum Hamming distance between valid symbols is 3 for a Hamming code without parity bit, and 4 for a Hamming code with parity bit.
A notation for error correcting codes exists, where a [t, i, d] code is one which uses t-bit symbols, containing i bits of information, having a minimum Hamming distance of d between valid symbols. The sequence of Hamming codes is:
Without          With
Parity           Parity
[7,4,3]          [8,4,4]
[15,11,3]        [16,11,4]
[31,26,3]        [32,26,4]
[63,57,3]        [64,57,4]
[127,120,3]      [128,120,4]
[255,247,3]      [256,247,4]
n    n           n  n
[2 -1,2 -n-1,3]  [2 ,2 -n-1,4]
As the total length of a symbol is 2^n for a code with parity, this means that even though the number of check bits is small, if one wishes to use a Hamming code for error checking in a computer memory with a word length that is a power of two, one has just slightly gone past the limit for using a certain number of check bits.
Thus, for example, single error correction and double error detection for a 64-bit word requires eight check bits instead of seven. This is not too inconvenient a number to provide. Also, this inefficiency provides some freedom of choice to the designer.
The seven check bits in the [127,120,3] code without parity correspond, for each of the 120 data bits, to every possible combination of seven bits in which two or more of the bits are equal to one.
These combinations can be broken down by number of bits into the following categories:
Two bits:       21
Three bits:     35
Four bits:      35
Five bits:      21
Six bits:        7
Seven bits:      1
If one takes only the combinations with an even number of bits, there are 21 + 35 + 7 of them, or 63. This is, unfortunately, less than 64, but that still means one could have a code with parity bit based on a subset of the Hamming code where only one of the data bits determines if the error-correcting portion should have the same parity, or the opposite parity, as the rest of the data bits.
As noted above, one can obtain an equivalent code from the matrix for a code by replacing a row with the XOR of another row with itself. Doing this for a code with a parity bit will mean the code no longer has an explicit parity bit.
The additional flexibility this provides allows one to create a [72,64,4] code which has the additional property that the check bits always have odd parity. In fact, obtaining that property is now trivial, in itself.
U. S. Patent 3,623,155 is for a code of this type, devised by Mu-Yue Hsiao at IBM, which was optimized with great effort for far more important properties as well; maximizing the percentage of the time when four-bit errors are detected as errors instead of leading to a valid symbol (which will be most of the time in any case), and minimizing the percentage of the time when three-bit errors are assumed to be two-bit errors that can be corrected (this, unavoidably, will occur about half the time, but it can be worse), and allowing a reduction in the gate count, and in the maximum gate delay, required for an implementation. (It also had the property that the calculation of this error-correcting code could produce byte parity as a byproduct.)
This invention came after IBM had already produced at least two computer systems, the IBM 7030 (Stretch) and the IBM System/360 Model 85, which used a [72,64,4] code for memory error correction. It is far from the only attempt to improve upon the Hamming code for this purpose; more recently, another such code was devised by Shigeo Kaneda at Nippon Telegraph and Telephone. This code is called a SEC-DED-S4ED code, which means that, in addition to providing correction of a single bit error, and detection of a double-bit error, it will detect an error involving three or four bits, as long as they belong to the same 4-bit nybble of the 72-bit word fetched from memory. Anyone who has looked at a 72-pin memory stick, and found there were fewer than 36 chips on it, or a 168-pin DIMM, and found there were fewer than 72 chips on it, will appreciate the relevance of this property.
Intermediate between these two codes is one devised by D. C. Bossen at IBM at about the same time as Mu-Yue Hsiao developed his code; this one has the property of also correcting errors in two bits, if those two bits are adjacent.
The check bits for these three codes are shown below:
Mue-Yue Hsiao       D. C. Bossen        Shigeo Kaneda
1 1 0 1 0 0 0 0     1 0 0 1 0 0 0 0     1 0 0 0 0 1 0 1
1 1 0 1 1 1 0 0     0 1 1 1 0 0 0 0     0 1 1 0 1 0 1 1
1 1 1 0 1 1 0 0     1 0 1 1 0 0 0 0     0 0 1 0 0 1 0 1
1 1 1 0 0 0 0 0     0 1 1 0 0 0 0 0     1 0 0 1 1 1 1 0
1 0 0 1 1 0 0 0     1 0 1 0 0 0 0 0     0 1 0 0 0 1 0 1
1 0 0 1 0 1 0 0     0 1 0 1 0 0 0 0     1 0 0 1 1 0 1 1
1 0 0 1 0 0 1 0     0 1 0 0 1 0 0 0     0 0 0 1 0 1 0 1
1 0 0 1 0 0 0 1     1 1 0 0 0 1 0 0     0 1 1 0 1 1 1 0
0 1 1 0 1 0 0 0     1 1 0 0 1 0 0 0     1 0 0 0 1 0 1 0
0 1 1 0 0 1 0 0     1 0 0 0 0 1 0 0     0 1 1 0 0 1 1 1
0 1 1 0 0 0 1 0     1 0 0 0 1 0 0 0     0 0 1 0 1 0 1 0
0 1 1 0 0 0 0 1     0 1 0 0 0 1 0 0     1 0 0 1 1 1 0 1
1 1 0 0 1 0 0 0     1 0 1 0 1 1 0 1     0 1 0 0 1 0 1 0
1 1 0 0 0 1 0 0     0 1 0 1 1 0 1 1     1 0 0 1 0 1 1 1
1 1 0 0 0 0 1 0     1 0 1 0 0 1 1 1     0 0 0 1 1 0 1 0
1 1 0 0 0 0 0 1     0 1 0 1 1 1 1 0     0 1 1 0 1 1 0 1
0 0 1 1 1 0 0 0     0 1 1 0 1 0 0 0     1 0 0 0 0 0 1 1
0 0 1 1 0 1 0 0     1 1 0 1 0 1 0 0     0 1 0 0 1 1 1 1
0 0 1 1 0 0 1 0     1 1 1 0 1 0 0 0     0 0 1 0 1 1 0 0
0 0 1 1 0 0 0 1     1 0 0 1 0 1 0 0     0 0 0 1 1 1 1 1
1 0 1 0 1 0 0 0     0 0 0 1 1 0 1 0     1 0 0 0 1 1 1 1
1 0 1 0 0 1 0 0     0 0 1 1 0 1 0 1     0 1 0 0 0 0 1 1
1 0 1 0 0 0 1 0     0 0 1 1 1 0 1 0     0 0 1 0 1 1 1 1
1 0 1 0 0 0 0 1     0 0 1 0 0 1 0 1     0 0 0 1 1 1 0 0
0 1 0 1 1 0 0 0     1 0 0 0 0 1 1 0     0 1 0 0 0 1 1 0
0 1 0 1 0 1 0 0     0 1 0 0 1 1 0 1     1 0 0 1 1 0 0 0
0 1 0 1 0 0 1 0     1 0 0 0 1 1 1 0     0 0 0 1 1 0 0 1
0 1 0 1 0 0 0 1     0 1 0 0 1 0 0 1     0 1 1 0 0 0 1 0
1 0 1 1 0 0 0 0     1 0 1 0 0 0 0 1     1 0 0 0 1 1 0 0
1 0 1 1 0 0 1 1     0 1 0 1 0 0 1 1     0 1 0 0 1 1 0 0
0 1 1 1 0 0 1 1     1 0 1 0 0 0 1 1     0 0 1 0 0 0 1 1
0 1 1 1 0 0 0 0     0 1 0 1 0 0 1 0     0 0 0 1 0 0 1 1
0 0 0 0 1 1 1 0     1 0 1 0 0 0 1 0     0 1 0 1 1 0 0 0
1 1 0 0 1 1 1 0     0 1 0 1 0 0 0 1     1 0 1 1 0 1 1 0
1 1 0 0 1 1 0 1     1 0 1 0 1 0 0 0     0 1 0 1 0 0 1 0
0 0 0 0 1 1 0 1     0 1 0 1 0 1 0 0     1 1 1 0 1 0 0 1
1 0 0 0 1 0 1 0     1 0 0 0 1 0 1 0     0 1 0 1 0 1 0 0
0 1 0 0 1 0 1 0     0 1 0 0 0 1 0 1     1 0 1 1 1 0 0 1
0 0 1 0 1 0 1 0     0 0 1 0 1 0 1 0     0 1 0 1 0 0 0 1
0 0 0 1 1 0 1 0     0 0 0 1 0 1 0 1     1 1 1 0 0 1 1 0
1 0 0 0 0 1 0 1     0 0 0 0 1 0 0 1     1 0 1 0 1 0 0 0
0 1 0 0 0 1 0 1     0 0 0 0 0 1 1 1     0 1 1 1 0 1 1 0
0 0 1 0 0 1 0 1     0 0 0 0 1 0 1 1     1 0 1 0 0 0 1 0
0 0 0 1 0 1 0 1     0 0 0 0 0 1 1 0     1 1 0 1 1 0 0 1
1 0 0 0 1 1 0 0     0 0 0 0 1 0 1 0     1 0 1 0 0 1 0 0
0 1 0 0 1 1 0 0     0 0 0 0 0 1 0 1     0 1 1 1 1 0 0 1
0 0 1 0 1 1 0 0     0 0 0 1 0 0 1 0     1 0 1 0 0 0 0 1
0 0 0 1 1 1 0 0     0 0 1 1 0 0 0 1     1 1 0 1 0 1 1 0
1 0 0 0 0 0 1 1     0 0 1 1 0 0 1 0     0 0 1 1 1 0 0 0
0 1 0 0 0 0 1 1     0 0 1 0 0 0 0 1     1 1 1 1 0 1 0 0
0 0 1 0 0 0 1 1     0 0 1 0 0 0 1 0     1 1 0 0 0 0 1 0
0 0 0 1 0 0 1 1     0 0 0 1 0 0 0 1     1 1 1 1 0 0 0 1
1 0 0 0 0 1 1 0     0 0 1 0 0 1 0 0     1 1 1 1 1 0 0 0
0 1 0 0 0 1 1 0     0 0 0 1 1 1 0 0     0 0 1 1 0 1 0 0
0 0 1 0 0 1 1 0     0 0 1 0 1 1 0 0     1 1 1 1 0 0 1 0
0 0 0 1 0 1 1 0     0 0 0 1 1 0 0 0     1 1 0 0 0 0 0 1
1 0 0 0 1 0 0 1     0 0 1 0 1 0 0 0     0 1 1 0 0 1 0 0
0 1 0 0 1 0 0 1     0 0 0 1 0 1 0 0     1 0 0 0 1 0 0 1
0 0 1 0 1 0 0 1     0 1 0 0 0 0 1 0     1 0 0 1 0 0 0 1
0 0 0 1 1 0 0 1     1 1 0 0 0 0 0 1     0 0 1 0 0 1 1 0
0 0 0 0 0 1 1 1     1 1 0 0 0 0 1 0     1 1 0 0 1 0 0 0
0 0 1 1 0 1 1 1     1 0 0 0 0 0 0 1     1 1 0 0 0 1 0 0
0 0 1 1 1 0 1 1     1 0 0 0 0 0 1 0     0 0 1 1 0 0 1 0
0 0 0 0 1 0 1 1     0 1 0 0 0 0 0 1     0 0 1 1 0 0 0 1
The Golay Code
Only one other perfect code for binary signals, significantly distinct from those we have examined so far, the Hamming code, a parity bit, and multiple repetition, is possible, the binary Golay code. It takes a 12-bit input, and adds 11 error-checking bits to it. Like the Hamming codes, an extra parity-check bit can be added, and the code remains optimal; however, the term perfect is only applied to the Golay code and Hamming codes without the parity bit, and the trivial code involving an odd number of repetitions. There are also nonlinear codes which involve the same number of bits, and correct the same number of errors, as the Hamming codes, but which are distinct from them, which are perfect; for practical purposes, there would be no reason to use them instead of the Hamming code, but of course this is still a result of great theoretical importance: and as for practical applications of nonlinear codes, the Preparata codes are examples of nonlinear codes the performance of which cannot be equalled by that of a linear code.
The number of possible combinations of three or fewer bits in error over a block of 23 bits is the following:
No bits in error:
1
One bit in error:
23
Two bits in error:
23 * 22
--------- = 23 * 11 =           253
2 *  1
Three bits in error:
23 * 22 * 21
-------------- = 23 * 11 * 7 = 1771
3 *  2 *  1
----
Total:     2048
and so the total, 2,048, is precisely the number of possible values of the 11 bits used for error checking.
As the Golay code uses a block of 23 bits, with 12 bits used for data (and therefore 2^12 possible valid codewords), and it corrects three errors, which means that the minimum Hamming distance between valid codewords is 7, it is referred to as a [23,12,7] code. Similarly, the code consisting of triple repetition is a [3,1,3] code, that of quintuple repetition is a [5,1,5] code, that of septuple repetition is a [7,1,7] code, and so on. The Hamming codes all have distance 3, and the three illustrated above are [7,4,3], [15,11,3], and [31,26,3] codes. In general, for N error-correcting bits, the corresponding Hamming code is a [(2^N)-1,(2^N)-N-1,3] code.
It is only possible to have codes that approach the effectiveness of the perfect codes due to the existence of symmetric arrangements of codewords; thus, [7,2,5], [10,4,5], [15,8,5] and [31,22,5] codes, for example, as might be thought to exist from the number of possible combinations of two or fewer bits in error for words of various lengths, are not necessarily available.
A modified form of the Golay code with parity bit added, so that the parity bit is no longer explicitly visible, is shown in a book by two of the three co-authors of the Handbook of Applied Cryptography, and an equivalent form, modified by some rearrangement of rows and columns (to obtain a shifting of the cyclic 11 by 11 portion of the error-checking matrix, and to put the row and column of 1 bits in a more conventional position) is shown here:
1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 1 0 0 0 1
0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 1 1
0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 1 0 1
0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1
0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 1 1 1
0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 1 1 0 1
0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 1 1 0 1 1
0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 1 0 1 1 1
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 0 1 1 1 1
0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 1 0 1
0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 1 1 1 0 0 1
0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0
In this code, the minimum Hamming distance between valid codewords is eight; without the parity bit, it would be seven.
A distance of seven allows either correcting three errors, correcting two errors and detecting two errors, correcting one error and detecting four errors, or detecting six errors.
A distance of eight allows either correcting three errors and detecting one error, correcting two errors and detecting three errors, correcting one error and detecting five errors, or detecting seven errors.
Examine the error-checking portion, the second square half, of the matrix for the Golay code shown above. The right and bottom edges consist of all ones except for a zero where they meet.
The remaining 11 by 11 square consists of the sequence<PHONE_NUMBER>0 repeated in every row, but shifted one space to the left in each row. This sequence contains exactly six one bits, an even number.
The matrix is symmetric, hence unchanged when flipped around the diagonal running from the top left to the bottom right.
Hence, the fact that every row contains an odd number of 1 bits, the last row ANDed with any other row produces a row with six one bits, and any two of the first 11 rows, when combined by an AND, produces a rotated version of one of the following strings:
10110111000 and<PHONE_NUMBER>1 =<PHONE_NUMBER>0 (3 bits)
10110111000 and<PHONE_NUMBER>0 =<PHONE_NUMBER>0 (3 bits)
10110111000 and<PHONE_NUMBER>1 =<PHONE_NUMBER>0 (3 bits)
10110111000 and<PHONE_NUMBER>1 =<PHONE_NUMBER>0 (3 bits)
10110111000 and<PHONE_NUMBER>0 =<PHONE_NUMBER>0 (3 bits)
10110111000 and<PHONE_NUMBER>1 =<PHONE_NUMBER>0 (3 bits)
10110111000 and<PHONE_NUMBER>1 =<PHONE_NUMBER>0 (3 bits)
10110111000 and<PHONE_NUMBER>1 =<PHONE_NUMBER>0 (3 bits)
10110111000 and<PHONE_NUMBER>0 =<PHONE_NUMBER>0 (3 bits)
10110111000 and<PHONE_NUMBER>0 =<PHONE_NUMBER>0 (3 bits)
preceded by a single 1 bit, means that, using modulo 2 arithmetic, the error-checking matrix in the code as represented here is its own inverse. (If it weren't for that extra zero, a different decoding matrix would be required, and a slightly more complicated version of the decoding procedure given below would be required.) Because of the symmetry around the diagonal, this is true both in the usual convention for matrix multiplication (numbers go in from the top, and come out on the right) and the one used for error-correcting codes (numbers go in from the left, and come out on the bottom). For more information on matrix multiplication, see the section concerning the Hill Cipher.
This helps to make it practical to check a codeword formed by this code, and then transmitted, for errors. The following procedure will find the correct original 12-bit input if there were three or fewer errors in the transmitted 24-bit block, or it will fail if there were four errors. (With more than four errors, of course, it can be fooled.)
First, take the first half, and put it through the code, to see what the codeword would have looked like, if the first half containing the actual data happens to be perfectly without error. Since we are able to correct up to three errors, if the error-checking part of this result differs by no more than three bits from what was recieved, all the errors (if any) happened in the error-checking part, so the data as recieved can be accepted.
Second, take the second half, and put it through the code. Since the error-checking part of the matrix is its own inverse, the error-checking half of the result will be what the data was supposed to have been, if the error-checking half of the block was recieved perfectly without error. If that result differs by no more than three bits from what was recieved in the data portion of the block, then the data as recovered from the error-checking part can be accepted.
Third, consider the possibility that there were errors in both the data and error-checking part of the block. With three errors it is possible that there could be one error in one of the two parts of the block, and two errors in the other part. So, decoding continues by a limited amount of trial and error. Here, we will assume that exactly one bit in the data portion of the block is in error. Thus, we will take the data portion of the block, and for each of the 12 bits of it in turn, we will invert that bit, put the result through the code, and compare the error-checking portion of the result with that recieved. If the result is two or fewer errors in the error-checking portion then the right bit has been found, and the data portion with the bit you flipped is correct.
Fourth, assume that exactly one bit in the error-checking portion of the block is in error, and for each of the 12 bits in the error-checking portion, invert that bit, apply the code to the result, and compare the error-checking portion of the output to the data portion of the recieved block. If two or fewer errors are found, then the data calculated from the error-checking portion with one flipped bit contains the correct data.
Of course, this involves counting the number of 1 bits in the XOR of the expected error-checking bits or the expected data bits and those actually received. This step can be time-consuming. One could speed it up by using a table with 4,096 entries, in which one could swiftly look up the number of one bits in a 12-bit word.
Of course, that could be made more manageable by using a table with 64 entries twice, for each half of the word. But if one were reconciled to using a table with 4,096 entries, then one could decode the Golay Code more swiftly.
The XOR of the expected error-checking bits with those actually received is called the syndrome of a received codeword. The entries in a table, indexed by the syndrome, corresponding to combinations with 0, 1, 2, or 3 bits equal to 1, could contain 0, indicating that all the errors, if there actually are three or fewer errors in the block, are in the error-checking portion of the codeword.
For the case of one error in the data portion, place the binary value<PHONE_NUMBER>00, indicating the first data bit is to be flipped, in all locations derived from XORing the first row of the error-checking part of the matrix with every combination of bits involving 0, 1, or 2 bits equal to 1, and then the binary value<PHONE_NUMBER>00 in all locations derived from XORing the second row of the error-checking part of the matrix with every combination of bits involving 0, 1, or 2 bits equal to 1, and so on.
Similarly, for two errors in the data portion, combine the XORs of two different rows in the error-checking portion of the matrix with either 0 or a single bit equal to 1 to produce the indexes for every combination of two bits in error in the data portion as indicated by those two rows in the error-checking portion of the matrix.
Finally, for three errors in the data portion, all combinations of three distinct rows in the error-checking portion of the matrix would index to the corresponding arrangement of three errors in the data portion.
The remaining entries in the table would indicate that there may be four errors, which cannot be corrected, only detected, so an invalid value would be placed in those portions of the table as a flag. Any value with more than three one bits could be tested for directly, so the entries do not need to be more than twelve bits long.
Another perspective on the binary Golay Code, which I also found understandable, is contained in this thesis. In the form of the Golay Code given above, eleven rows are cyclic, and one special, in the error-checking matrix; in the form discussed in that thesis, all twelve rows are equivalent, but as they relate to the faces of a dodecahedron, there is no way to put them in a cyclic order.
The form of the Golay code discussed there is:
1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 1
0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 1 1 1
0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 1 1 1
0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 1 1
0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1
0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 1 1 1 0 1
0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 1 0 1 0 1 1 0 0
0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 1 0 1 0 1 1 0
0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 0
0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1 1 0 1 0 0
0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 0 0 1 1 0 1 0
0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 1
Each of the twelve rows and columns of the error-checking part of the matrix corresponds to a face of the dodecahedron, and it contains a zero for every pair of faces that are next to one another. (A face is not considered to be next to itself.) This is still a Golay code, with the same error-correcting property of a Hamming distance of 8 between codewords, and not only is the error-checking matrix symmetric, but once again it is its own inverse as shown here. Because of the dodecahedral symmetry, once again, it is only necessary to AND one row of the matrix with the eleven other rows to establish that. For example, row 1 shares four bits with rows 2 to 11, and two bits with row 12.
But being self-dual is not a necessary property of a Golay code; either example of a Golay code given here would still be a Golay code if the error-checking matrix were reflected left to right, since the error-checking properties would be identical, but then that matrix would not be its own inverse.
This site contains a link to a paper in DVI format giving eight different constructions of the binary Golay code. (Unfortunately, you may have difficulty in viewing documents in DVI format on your system.)
The following representation of the Golay code is the one actually used in MIL-STD-188-141A and FED-STD-1045, as well as being proposed for use in ITU H.223, and thus it may be widely used for purposes involving radio communications:
1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 1 1
0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0
0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 1 0 1 1
0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 1 0
0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 0 1
0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 1
0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 1
0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 1 1 0 1
0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 1 1 1
The error-checking part of the matrix is not symmetric along the main (upper left to lower right) diagonal, and its transpose is shown as being used in decoding. Also, it is said to have been generated from the polynomial
11  9  7  6  5
x  +x +x +x +x +x+1
or, according to another source, on the polynomial
11  10  6  5  4  2
x  +x  +x +x +x +x +1
which correspond to the following sequence of bits, either in order or reversed:
1 0 1 0 1 1 1 0 0 0 1 1
which indeed is the first row of the error-correcting matrix.
If you look at the first eleven columns, when the eleventh column is a 0, the first column in the next row is a 0, and bits 2 to 11 of that row are the same as bits 1 to 10 of the row the eleventh column of which is a 1. When the eleventh column is a 1, after shifting the first 11 bits one place to the right, the first 11 bits of the next row are obtained by the XOR of<PHONE_NUMBER>1 with those bits, so we are seeing powers of two modulo the polynomial
11  10  6  5  4  2
x  +x  +x +x +x +x +1
with their bits reversed. If we proceed from the bottom up, we can use left shifts, but we are no longer starting with the polynomial itself.
Each column has seven ones in it, so when multiplied by its transpose, there will be a 1 in every position on the diagonal in the result. Any two distinct columns have either four or two ones in common, (as I had to verify by brute force with a short BASIC program) and so the transpose of the error-checking part of the matrix is indeed also the inverse of that part.
This explains the contents of the twelfth column of the error-checking part of the matrix; the bit in it is a one if there are only six ones in the rest of the row, and a zero if there are seven, so it is an odd parity bit for the row.
Despite the fact that each column and row contains seven ones, the error matrix can't be produced simply by rearranging rows and columns of the one produced from the dodecahedron. This can be shown because the columns corresponding to opposite faces can be identified (no zeroes in the same row), and two non-opposite faces must be adjacent to two other faces, and those two faces must be adjacent to three other (than the first two: those two faces may be adjacent to each other if the two non-opposite faces were not adjacent) faces each, two from each group of which are opposite to two from the other group (which is the point at which it breaks down if you start with the first two columns).
Error-checking in this case involves the use of the inverse of the error-checking part of the matrix, but otherwise the algorithm is the same as the one given above.
A form of the Golay Code as a (23,12) code, without the parity bit added, is the following, based on the one from the original paper in which Marcel Golay of the Signal Corps described this error-correcting code in 1949.
             A A A A B B B C C D
             B C D E C D E D E E

1 0 0     0 0    0 0 0 0 1 1 1 1 1 1   A       1
0 1 0 ... 0 0    0 1 1 1 0 0 0 1 1 1   B       1
0 0 1     0 0    1 0 1 1 0 1 1 0 0 1   C       1
1 1 0 1 1 0 1 0 1 0   D       1
1 1 1 0 1 1 0 1 0 0   E       1
             0 1 0 1 0 1 1 1 0 0   ABCED   1
             0 1 1 0 1 0 1 0 0 1   ABDCE   1
             0 0 1 1 1 1 0 0 1 0   ABEDC   1
             1 0 1 0 0 0 1 1 1 0   ACBDE   1
             1 0 0 1 1 0 0 1 0 1   ACEBD   1

0 0 0 ... 1 0    1 1 0 0 0 1 0 0 1 1   ADCBE   1
0 0 0 ... 0 1    1 1 1 1 1 1 1 1 1 1           0
On one side is the identity matrix, abbreviated in this diagram. Note that the column of all ones except for a zero at the bottom, is part of the basic structure of the code, so the column representing the parity bit is hidden elsewhere in the preceding examples. (This seems astounding, as one would think that if one added a parity bit to this code as it stands, the result would be wasteful instead of perfect, given its similarity to that column.)
AB to DE are the various combinations of two different objects from a set of five. The first five rows represent when one of the five objects is not part of that pair of objects.
The next six rows represent when that pair of objects, or its reversal, is not present in one of the six different distinct odd permutations of the five objects that exist when cyclic permutations are ignored. Thus, ABCED in the chart above stands for ABCED, BECDA, CEDAB, EDABC, and DABCE, and so DA, the reversal of AD is considered to be a part of it.
Then there is the row with all ones except for that single zero in the last column.
Through rearrangement of rows and columns, one can obtain from that version of the Golay Code, but with the parity bit added, the following version:
1 0 0 0 0 0 0 0 0 0 0 0   1 1 1 1 1 1   0 0 0 0   1   1   A
0 1 0 0 0 0 0 0 0 0 0 0   0 0 0 1 1 1   0 0 1 1   1   1   ABEDC
0 0 1 0 0 0 0 0 0 0 0 0   0 1 1 0 0 1   0 1 0 1   1   1   ABCED
0 0 0 1 0 0 0 0 0 0 0 0   1 0 1 0 1 0   0 1 1 0   1   1   ABDCE
0 0 0 0 1 0 0 0 0 0 0 0   1 1 0 0 1 0   1 0 0 1   1   1   ACEBD
0 0 0 0 0 1 0 0 0 0 0 0   0 1 1 1 0 0   1 0 1 0   1   1   ACBDE
0 0 0 0 0 0 1 0 0 0 0 0   1 0 0 1 0 1   1 1 0 0   1   1   ADCBE
0 0 0 0 0 0 0 1 0 0 0 0   1 1 0 1 0 0   0 1 1 1   1   1   B
0 0 0 0 0 0 0 0 1 0 0 0   1 0 1 0 0 1   1 0 1 1   1   1   C
0 0 0 0 0 0 0 0 0 1 0 0   0 0 1 1 1 0   1 1 0 1   1   1   D
0 0 0 0 0 0 0 0 0 0 1 0   0 1 0 0 1 1   1 1 1 0   1   1   E
0 0 0 0 0 0 0 0 0 0 0 1   1 1 1 1 1 1   1 1 1 1   0   1
                      D C B C B B   A A A A   s   p
                      E D E E C D   B C D E

Not only is the parity bit, the simplest error-correcting code, present explicitly, but also present is the Hamming code for eleven of the data bits. (Incidentally, I discovered, in preparing this, an error in my description of Golay's original version of his code above; I had originally failed to recognize that AD is contained within ADCBE.) Note also that the first six columns of the error-correcting part of the matrix, in addition to containing two occurrences of 111111, also contain ten of the twenty combinations possible within a three-of-six code, so here the Golay code is divided up into several older and less-sophisticated codes.
The presence of an explicit parity bit can be used to shrink the table with 4,096 entries used for decoding down to one with only 2,048 entries; this table would indicate, for the first 11 error-checking bits, the correction to the data bits which the discrepancy in them would imply, but what would also be noted is whether the error to be corrected would also change the parity, and how many bits are in error. If three bits are in error, and the parity is also not what would be expected, then an error can only be detected.
It should be possible to make use of the three-of-six code and the Hamming code portions as well to produce an algorithm for decoding that would be quite efficient while only involving relatively short tables.
The bits shown in bold show where even the AUTOSPEC code can be seen as embedded within it! There is also a relationship between Golay codes and Hadamard codes as well.
It would actually be preferable to have the supplementary Golay bit as the first of the error correcting bits to produce a "conventional" version of the Golay code; it is placed as the second-last bit here in order that the AUTOSPEC code would be visible.
With the aid of the inverse of the error-correcting part of the matrix, one can decode this code using basically the same algorithm as used in the first case, but, in addition, for the common case of only a few errors, decoding can be made simpler by using only the Hamming error-correcting biits first.
The inverse of the error-correcting part of the matrix shown above is:
1 1 1 0 0 1 0 1 1 0 0 0
1 1 0 1 0 0 1 1 0 0 1 0
1 1 0 0 1 0 1 0 1 1 0 0
1 0 1 1 1 0 0 1 0 1 0 0
1 0 1 0 0 1 1 0 0 1 1 0
1 0 0 1 1 1 0 0 1 0 1 0
0 1 1 1 0 0 0 0 1 1 1 0
0 1 0 0 1 1 0 1 0 1 1 0
0 0 1 0 1 0 1 1 1 0 1 0
0 0 0 1 0 1 1 1 1 1 0 0
1 0 0 0 0 0 0 1 1 1 1 1
0 1 1 1 1 1 1 0 0 0 0 1
While it no longer has a parity bit, or a supplemental Golay bit, the three-of-six code and the Hamming error-correction bits are still visible in the inverse, which has the structure:

g g g g g g h h h h *
Additional Error-Correcting Codes

There are a number of other codes used for error detection and correction. Examples of codes used in the same kind of form as used with Hamming codes include Hadamard codes and Reed-Muller codes. These codes all add slightly more redundancy than is required for the error-checking they seek to attain.
Hadamard Codes
An example of a Hadamard code looks like this:
00000 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
00001 | 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
00010 | 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
00011 | 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
00100 | 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
00101 | 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0
00110 | 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0
00111 | 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1
01000 | 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
01001 | 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0
01010 | 0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 0
01011 | 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1
01100 | 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0
01101 | 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1
01110 | 0 0 1 1 1 1 0 0 1 1 0 0 0 0 1 1
01111 | 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
10000 | 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
10001 | 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
10010 | 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0
10011 | 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1
10100 | 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0
10101 | 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1
10110 | 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1
10111 | 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0
11000 | 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
11001 | 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1
11010 | 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1
11011 | 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0
11100 | 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1
11101 | 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0
11110 | 1 1 0 0 0 0 1 1 0 0 1 1 1 1 0 0
11111 | 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
These codes are obtained by a procedure similar to that used to create fractal designs:
                   1 1   1 1

1 1                 1 0   1 0
1 0  - becomes -->
1 1   0 0
1 0   0 1
applied as many times as desired, and then the result has its complement appended to it. Mariner 9 used the code of this type that occupies a 32 by 64 matrix. This method only generates Hadamard codes of orders which are powers of 2. Hadamard codes and matrices of many other orders which are multiples of 4 are also known, and it is conjectured, but not yet proven, that one exists for every such order. These Hadamard codes are obtained by other, more difficult methods.
Note that here we are not creating a generator matrix for the code, but the actual table of codewords. Thus, Hadamard codes are useful when it is desired to construct a code that contains a large proportion of error correction; thus, for example, the code used by Mariner 9 used 32 bits of signal to represent only 6 bits of data.
Thus, the example above, which expands five bits to sixteen, is perhaps the smallest which exhibits the unique strength of this code in providing efficient codes which protect very strongly against errors.
In fact, however, the example above shows that the code is a linear code, so it can be expressed more compactly than the full table given above. The encoding matrix for the code is simply:
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
thus, in general, the matrix for a Hadamard code is composed of the representations of the binary numbers in order to encode all but the last bit of the block, and the last bit, when present, inverts the entire output block.
One can turn a Hadamard code into a more conventional-looking error correcting code by rearranging columns, and XORing all the other rows to the last row, to cause the last row to have zeroes in it wherever there is exactly one other one in the column (as well as when the number of ones elsewhere is odd); the result in the case of the Hadamard code for five data bits could be something such as the following:
1 0 0 0 0 0 0 0 1 1 1 0 1 1 1 1
0 1 0 0 0 0 1 1 0 0 1 1 0 1 1 1
0 0 1 0 0 1 0 1 0 1 0 1 1 0 1 1
0 0 0 1 0 1 1 0 1 0 0 1 1 1 0 1
0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 1
which contains part of a Hamming code turned sideways.
Note that only when the number of data bits is odd does this approach produce a true parity bit as part of the code.
More About the Golay Code
Incidentally, this representation of the Hadamard code for five data bits can also be found embedded in the conventionalized Golay code shown above:
1 0 0 0 0 0 0 0 0 0 0 0   1 1 1 1 1 1   0 0 0 0   1   1   A
0 1 0 0 0 0 0 0 0 0 0 0   0 0 0 1 1 1   0 0 1 1   1   1   ABEDC
0 0 1 0 0 0 0 0 0 0 0 0   0 1 1 0 0 1   0 1 0 1   1   1   ABCED
0 0 0 1 0 0 0 0 0 0 0 0   1 0 1 0 1 0   0 1 1 0   1   1   ABDCE
0 0 0 0 1 0 0 0 0 0 0 0   1 1 0 0 1 0   1 0 0 1   1   1   ACEBD
0 0 0 0 0 1 0 0 0 0 0 0   0 1 1 1 0 0   1 0 1 0   1   1   ACBDE
0 0 0 0 0 0 1 0 0 0 0 0   1 0 0 1 0 1   1 1 0 0   1   1   ADCBE
0 0 0 0 0 0 0 1 0 0 0 0   1 1 0 1 0 0   0 1 1 1   1   1   B
0 0 0 0 0 0 0 0 1 0 0 0   1 0 1 0 0 1   1 0 1 1   1   1   C
0 0 0 0 0 0 0 0 0 1 0 0   0 0 1 1 1 0   1 1 0 1   1   1   D
0 0 0 0 0 0 0 0 0 0 1 0   0 1 0 0 1 1   1 1 1 0   1   1   E
0 0 0 0 0 0 0 0 0 0 0 1   1 1 1 1 1 1   1 1 1 1   0   1
                      D C B C B B   A A A A   s   p
                      E D E E C D   B C D E

in this case, split up, and with some trivial rearrangement of rows and columns.
This illuminates something else about this representation of the Golay code, and suggests a further rearrangement of rows and columns to achieve the following:
1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1
0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 0 1 1 1  ABEDC
0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1  ABCED
0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 1 1 0 1  ABDCE
0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 0 0 1 1  ACEBD
0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 0 1  ACBDE
0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 1 1 1 1 0 0 1  ADCBE
0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 0 1 1 1 1  B
0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 0 1 1 0 1 1 1  C
0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 1  D
0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 0 1 1 1 0 1  E
0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1  A
                    s B B B C C D A A A A p
                      C D E D E E B C D E

in which the error-correcting part only just misses being its own transpose. In addition to the vector for the last data bit not being all ones in the parity-check area, to match the parity bit, note the structure of the highlighted six entries in the three-of-six code portion: the main diagonal is all ones, and except for the opposing diagonal of all zeroes, the other bits would all be inverted by transposition.
Here is an image of this representation of the Golay code, with color highlighting its symmetries and distinguishing its components:
Here is the inverse of the error-correcting part of this code:
1  0  0  0  0  0  0  1  1  1  1  1
0  0  1  0  0  1  1  0  0  1  1  1
0  0  0  1  1  1  0  0  1  0  1  1
0  1  0  0  1  0  1  0  1  1  0  1
0  1  0  1  0  0  1  1  0  0  1  1
0  0  1  1  1  0  0  1  0  1  0  1
0  1  1  0  0  1  0  1  1  0  0  1
0  1  1  1  0  0  0  0  1  1  1  0
0  1  0  0  1  1  0  1  0  1  1  0
0  0  1  0  1  0  1  1  1  0  1  0
0  0  0  1  0  1  1  1  1  1  0  0
1  1  1  1  1  1  1  0  0  0  0  0
Note how the Hamming portion stays in place, and the Hadamard portion is flipped vertically. And in the six-by-six square highlighted above, the two diagonals are inverted, and the rest of the bits remain unchanged.
So far, the error-correcting codes we have examined are designed around the assumption that single-bit errors are completely random and independent. In practice, of course, burst errors which affect several consecutive bits are more likely than errors involving the same number of bits in isolation.
One way of dealing with this is called interleaving, as was referred to briefly above. This is used, for example, in the encoding scheme for the Compact Disc. A very simple example of interleaving is used in the AUTOSPEC radio teletypewriter transmission format.
As seen previously, that format uses an error-correcting code with the matrix:
1 0 0 0 0 0 1 1 1 1
0 1 0 0 0 1 0 1 1 1
0 0 1 0 0 1 1 0 1 1
0 0 0 1 0 1 1 1 0 1
0 0 0 0 1 1 1 1 1 0
which has the easy-to understand result that a five-bit character with odd parity is transformed to itself followed by its inverse, and a five-bit character with even parity is transformed to two repetitions of itself, so that five bits convey information about the parity of the character, and then every bit is almost repeated twice.
In actual AUTOSPEC transmission, the ten-bit character codes are transmitted in ten-bit blocks with interleaving, so that for a given character, the first bit of the character's code is the first bit of one block, the second bit of the character's code is the second bit of the next block, and the third bit of the character's code is the third bit of the block after that, and so on.
Thus, a burst error ten bits long becomes ten single-bit errors in the codes of ten consecutive characters, and this code can correct single-bit errors.
The decoding algorithm is simple: by comparing the first five bits to the last five bits of a character, determine the parity of the data character. If the data bits have the wrong parity, then the values indicated by the error-correcting bits have priority; if they have the right parity, they are assumed correct.
If more than one error is found in either the error-correcting bits or in the data bits, however, some additional complexity is needed to handle the error in the best fashion.
Since 00000 has even parity, its error correcting bits are also 00000; on the other hand, 11111 is also followed by 00000, and thus 11111 could be used by convention as a synchronization character (although 11100 00011, for example, is also a valid code, the idea is that only multiple repetitions of 11111 would be expected by the receiver).
Bose-Chaudhuri-Hocquenghem Codes
The Golay code and the Hadamard codes both produce as many check bits as data bits. Normally, for protecting an enciphered message in transit, only a small number of check bits applied to a group of data bits are desired. The Bose-Chaudhuri-Hocquenghem codes are a family of error-correcting codes that allow one to devise codes similar to the Hamming code, but with a higher proportion of check bits.
The sequence of Hamming codes without a parity bit added are codes of the type:
n    n
[2 -1,2 -n-1,3]
which can be used to correct one error, and the addition of a parity bit allows detecting two errors as well.
The primitive Bose-Chaudhuri-Hocquenghem codes can be of the types:
n    n
[2 -1,2 -2n-1,5]
n    n
[2 -1,2 -3n-1,7]
n    n
[2 -1,2 -4n-1,9]
and so on. As with the Hamming codes, a parity bit can be added, and if the number of bits one wishes to send in a block are not of the form 2^n-Xn-1, where X are the number of errors to be corrected, rows can be omitted. As the number of errors to be corrected increases, BCH codes may no longer be the optimum codes for correcting a given number of errors, but for small values, they provide very good codes.
BCH codes are based on primitive polynomials in the Galois Field over 2^n, which were discussed earlier in the sections on the Rijndael block cipher, and on linear-feedback shift registers, and in a section of their own.
Because a BCH code is a cyclic code, when expressed in systematic form, in which parity-check bits are appended to the original data, it can be implemented, for encoding, in the same way as a cyclic redundancy check code; but as a cyclic redundancy check is simply used to reject an entire block if it is wrong, while a BCH code is used to correct errors, decoding a BCH code is more complicated.
We can compare the [31,26,3] Hamming code, in the form it has when produced as a case of the BCH code:
1 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 1 0 0 1 0
0 1 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 1 0 0 1
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 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 1 0 0 1 0 1 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 1 0 0 1 0 1
to the [31,21,5] BCH code:
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 1 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 1 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 1
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 1
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 1 1 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 1 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 1 0 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 1 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 0 1 0 0 1
and the [31,16,7] BCH code:
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 1 1 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 1 1 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 1 1
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 1 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 1 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 1 0 1 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 1 0 1 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 1 0 1
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 0 0 1 1 0 1
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 1 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 1
all shown in the form they would have as CRC codes; thus, the modular polynomial is visible in the bottom row.
If one wished to devise a code for protecting a computer memory consisting of words that were 256 bits wide, a starting point would be the BCH codes with a block size of 511 bits. Given existing computer memories with one parity bit for eight data bits, we have already seen that when the width of a data word was increased to sixty-four bits, it was possible to use the [127,120,3] Hamming code, with seven check bits, as a starting point, adding parity to make a [128,120,4] code, and then removing data bits to make a [72,64,4] code. In the case of data words 256 bits wide, similarly, the [511,484,7] BCH code can be used as a starting point; add a parity bit, to make a [512,484,8] code which corrects three errors and detects four errors, and then remove data bits to make a [284,256,8] code. This leaves four additional bits available, if one is using existing memory modules that allow for a 12.5% overhead for error correction.
Improving on BCH
Starting from the [255,239,5] BCH code for data words 128 bits wide, if one wished to make an error-correcting code that corrected up to two errors, and detected up to three errors, one would have to add a parity bit to the sixteen check bits already present in the [255,239,5] code.
However, IBM managed to devise a DEC-TED code for 128 bit data words that not only required only sixteen check bits, but which also had the desirable property as the (72,64) code by Shigeo Kaneda described above, of being able to detect errors of four bits confined to a single aligned block of four bits.
As that is a (144,128) code, it can use the same standard 72-bit memory parts that are used for conventional SEC-DED error-correction coding, but with a considerably stronger resistance to soft errors.
This code was described in U. S. Patent 4,509,172.
Some b-Adjacent Codes
Primitive polynomials over Galois fields are very useful in the construction of error-correcting codes; the theory of BCH codes involves them, and they are also the basis of Reed-Solomon codes.
A primitive polynomial, as we have seen elsewhere on this site, can be used as the basis for a shift register with a maximal period.
The operation of a shift register can be expressed by a matrix, and such a matrix is known as the companion matrix of the primitive polynomial.
Thus, the primitive polynomial x^4 + x + 1 over GF(16) has the companion matrix:
0 0 0 1
1 0 0 1
0 1 0 0
0 0 1 0
and multiplication of a vector of four bits by that matrix shifts the bits one place left, also XORing a copy of the leftmost bit into the rightmost position.
Since the shift register it simulates has maximal period, this means that each nonzero vector multiplied by that matrix produces a distinct output (so the matrix is invertible).
And that means that successive multiplications by that matrix will produce distinct outputs for a given input until all the possibilities have been generated.
This is a useful property for an error-correcting code.
When illustrating error-correcting codes, such as Hamming codes above, they're usually illustrated in a form like this:
1 0 0 0 0 1 1
0 1 0 0 1 0 1
0 0 1 0 1 1 0
0 0 0 1 1 1 1
Input bits come in from the left, an AND is performed with the number in each cell, and then XOR is done down the columns to produce the output. So, here, the diagonal matrix indicates where the data bits are just copied, and the last three columns show how the check bits are generated.
In normal matrix multiplication, though, the input comes in at the top, and the result goes out on the right. So sometimes just the columns used for the check bits are shown in ordinary matrix notation like this:
0 1 1 1
1 0 1 1
1 1 0 1
This makes it easier to express codes which are built up from matrices raised to powers.
Consider a code, described in this notation, with the structure:
I I       I    T T^2     T^14 T T^2     T^14
T T^2 ... T^14 I I   ... I    T T^2 ... T^14
T T^2     T^14 T T^2     T^14 I I       I
where T stands for the companion matrix for x^4 + x + 1 that we saw above, and I stands for the identity matrix.
This code produces 12 check bits for 168 data bits.
If we divide the code bits into aligned groups of four bits, and there is an error - whether it involves one bit, two bits, three bits, or all four bits, in just one of those groups of four bits, it can be corrected.
How would this be done?
If just one of the three groups of four bits in the check bits was in error, clearly the error is in the check bits, so they can be ignored, and the data bits taken as is.
For any error in the data bits that is confined to a single aligned group of four bits, the syndrome - the deviation of the check bits from their expected value based on the version of the data bits that is received - would consist of two nybbles that are the same, and one nybble that is different.
The nybble that is different represents the four bits of the error itself.
If it's in the first part of the check bits, the error is somewhere in the first 56 data bits; if it's in the second nybble, the error is in the second 56 data bits, and so on.
And, because of the maximal period property of the shift registers based on the primitive polynomial to which T is the companion matrix, the two nybbles that have the same data will have a different value for each of the fourteen nybbles in the group of 56 bits to which we have narrowed down the error.
The code in this example is of the kind known as a b-Adjacent code. Related codes that are guaranteed to detect some kinds of errors in addition to correcting others will be described next, as they have been found to be very useful in dealing with real-world errors in large computer memories.
Instead of looking for two nybbles the same, one could of course look for two nybbles that are nonzero, and use a code with this structure:
I I       I    0 0       0    T T^2     T^14
T T^2 ... T^14 I I   ... I    0 0       0
0 0       0    T T^2     T^14 I I       I
which is even simpler; here, the first of the two nybbles that are nonzero indicates the error, and the second one indicates its location within a group of 56 bits.
While the DEC-TED-S4ED code described earlier, based on a BCH code, is a major improvement over the conventional ECC, based on a Hamming code, normally used in computers today, IBM later devised a further improvement in error-correcting codes which is usually used instead when a better code than a SEC-DED code is desired.
The S4ED feature - detecting when a 4-bit wide memory chip has failed - has been noted as highly desirable. Thus, it would not be surprising that an S4EC feature - actually correcting the errors resulting from the failure of a 4-bit wide memory chip - would be even more desirable.
Initially, IBM devised an S4EC-D4ED code that was a (76,64) code, requiring 12 check bits to protect 64 data bits. This was described in U. S. Patent 5,757,823. It was originally used with System/390 mainframes, and thus the use of special memory parts was less of an issue. Later, codes with the S4EC-D4ED property that were (144,128) codes were devised, making this form of error correction highly practical, and, indeed, it is now offered by several companies in the computer industry.
In 1982, a paper described one such (144,128) code, of the type known as a Kaneda-Fujiwara code, and it was built out of the same matrices that I noted in the example above; its structure was equivalent to:
I    I    I    I    I    I    I    I    0    0    0    0    0    0    0    0
I    T    T^2  T^3  T^14 T^13 T^12 T^11 I    I    I    I    I    I    I    I
T^14 T^13 T^12 T^11 I    T    T^2  T^3  I    T    T^2  T^3  T^14 T^13 T^12 T^11
0    0    0    0    0    0    0    0    T^14 T^13 T^12 T^11 I    T    T^2  T^3
T^14 T^13 T^12 T^11 I    T    T^2  T^3  I    T    T^2  T^3  T^14 T^13 T^12 T^11
0    0    0    0    0    0    0    0    T^14 T^13 T^12 T^11 I    T    T^2  T^3
I    I    I    I    I    I    I    I    0    0    0    0    0    0    0    0
I    T    T^2  T^3  T^14 T^13 T^12 T^11 I    I    I    I    I    I    I    I
although the illustration in the original paper had the check bits associated with the data bits in a somewhat different order. To avoid excessive width, the check bits were split into two parts; those for the first 64 data bits are described on the top four lines, and those for the last 64 data bits on the bottom four lines.
Newer memory modules use DRAM chips that are eight bits wide instead of four bits wide. It is still possible to correct errors in a single package, but it is no longer possible to guarantee to correct all double errors in a (144,128) code. Therefore, it seems a simple brute-force approach involving interleaving can be used; for example, one might begin a code with the following structure:
I 0 I   0       I   0   T 0 T^2 0       T^7 0
0 I 0   I       0   I   0 T 0   T^2     0   T^7
T 0 T^2 0   ... T^7 0   I 0 I   0   ... I   0
0 T 0   T^2     0   T^7 0 I 0   I       0   I
Since T, T^2, up through T^14 are all distinct, with T^15 being the identity matrix, it is immediately obvious that the first 112 bits of data are recoverable by a code of this form. But since it is possible that whichever 8 bit group is in error might have an error in only four bits, or the same error in the first four bits and the second four bits, it is not immediately clear how one could devise the rest of the code.
However, continuing like this:
0 T 0   T^2
I 0 I   0
T 0 T^2 0
0 I 0   I
might initially appear to work.
In the case where only one nybble is in error, now the syndrome has two nonzero nybbles that are in opposite halves of its two bytes. That is clearly distinct.
In the case where both nybbles have exactly the same error, the two nybbles in one half aren't the same kind of multiple of the nybbles in the other half.
But could there be cases where error correction would fail when the two nybbles in one byte have different errors? Say when one error happens to be a power of T times the other error?
If an error in the second-last byte had an error of q in the first nybble, and Tq in the second nybble, then it is true that the fourth nybble of the syndrome would be T times the second nybble of the syndrome - just as it is for an error in the second nybble of the first byte.
However, the first nybble of the syndrome is also T times the third nybble of the syndrome, which is in the opposite direction.
So it does handle the case of two nybbles with different errors as well as a continuation such as:
I 0
0 I
0 T
T 0
which obviously fails when both nybbles have the same error, or
I 0
0 I
T 0
0 T^7
which obviously fails when the error in one nybble is zero.
What about this possibility, which might be considered simpler:
I 0   I   0
0 I   0   I
0 T^7 0   T^6
T 0   T^2 0
This, also, obviously works in the two possibly pathological cases; if both nybbles have the same error, or if one has no error.
But suppose the error in the second nybble of the second-last byte is T^6 times the error in the first nybble of the second-last byte. Then the third nybble of the syndrome will be T times the first nybble of the syndrome, just as in the case of an error in the first nybble of the first byte.
But the fourth nybble is also T times the first nybble, and the second nybble is not the same as the first nybble, so this also is distinguishable. So it seems as though this continuation should also work.
A Minor Mystery
Incidentally, one might wonder why so many bits have to be added to a code to increase the minimum Hamming distance between codewords from an even number to the next higher odd number, but increasing from an odd number to the next even number requires only adding one parity bit, even when the code providing a minimum distance between codewords that is that odd number is perfect.
The following diagram was an attempt to exhibit the full structure of the simplest Hamming code in all its seven-dimensional glory in an attempt to answer this,
but I am afraid that it is not particularly clear, there not being enough sufficiently distinctive colors among the 256 Internet-safe colors for its purpose.
Recent Error Correcting Codes
The field of error-correcting codes, like the field of data compression, is still a very active one, with new research being done and patents being issued on new methods.
Fire Codes
In the 1970s, a set of error-correcting codes called "Fire codes" were developed. One of the simplest of these could be used as a direct replacement for a parity bit, used with each character in many existing systems, providing error correction instead of just the detection of erroneous characters.

Each parity bit is the XOR of parity for the data byte with which it is associated and parity for staggered bits from the eight previous bytes. Essentially, it is a clever way to obtain the same results as are provided by the use of row and column parity bits. (After the last byte of data, one extra byte, with the extra parity bit, is needed to provide parity for all the remaining diagonals.)
More complicated forms involved XORing these parity bits with the parity of another group of eight bits, staggered by being from bytes separated by a larger distance.
Turbo Codes
A very recent exciting development in error-correcting codes is the class of codes known as "Turbo Codes". These were first presented by Berrou, Glavieux, and Thitimajshima in 1993.
As the first step in a Turbo Code, a copy of the data stream is divided into blocks of uniform length, and a known pseudorandom scrambling sequence is used to select at random a shuffle of the bits in each block.
The original data stream, and the shuffled data stream, are both fed separately into linear feedback shift registers to produce a constant stream of check bits.
A Turbo Code of rate 1/4 is obtained by sending all four sequences, the original data stream, the shuffled data stream, and the two sequences of check bits.
A Turbo Code of rate 1/3 is obtained by sending the original data stream and the two sequences of check bits.
A Turbo Code of rate 1/2 is obtained by using an independent pseudorandom scrambling sequence to select individual check bits from either of the two check bit sequences at random.
Since one could imagine circumstances where the random interleaving results in the data bits not being shuffled, or the selection of check bits at random provides parity for some data bits but not others, there is a temptation to modify the method somewhat from its ideal theoretical model. "NOISE"
"EXTERNAL_AUDITORY"

Thanks for the thesis @hollowprince-afk. Not sure what it has to do with this project, though?


Location is not published if app is in background

App stops sending the location update, if the app is in the background (Samsung SM-G900F)

Works for at least 5 minutes (did not check for longer period) on my OnePlus 5 - could it be, that Samsung has a more agressive task management?

visual studio killed the process, is working fine...


Change the spelling of container in the title

File: cloud/aci-container-features.md

Fixed in https://github.com/docker/compose-cli/commit/b70777abb9390a6b8450351b8dd7960a1c125949
If the issue has not been fixed, please let us know.


[App]: Identical tags appear in different colours

Current Behavior
Identical tags are assigned different colours in the run view.
Expected Behavior
One colour is assigned per tag
Steps To Reproduce

Create a number of runs with identical tags
Visit the runs table

Screenshots

Note: There are two tags assigned to each of these runs, the first one is sensitive so I don't want to show it - however this is the same tag in all cases.
Environment
OS: macOS and Ubuntu
Browsers: Chrome
Version: Any
Additional Context
Tags were logged as hardcoded strings from a Python script, so it's highly unlikely it's a problem on my end. I believe this issue happened a few weeks ago, then went away, but has now come back.

Hey @freddyheppell - just to make sure I'm understanding correctly: were you able to see all tags of the same string in the runs table appear in the same color a few weeks ago, then something changed to where the tags appear in different colors now?

I might be misremembering but I think previously identical tags were the same colour, then a few weeks ago they started showing as different colours. I was going to report it but then it reverted to showing them as the same colour before I could get round to it. Then, recently, it started happening again.

@freddyheppell - I wasn't able to reproduce the issue when adding tags programmatically. Could you run the following code snippet & let me know how this appears on your end?
import wandb

for i in range(5):
    wandb.init(project='colorTags', tags=['uma'])

    wandb.log({'point': i})

    wandb.finish()

Few questions to dig into this further:

Are you running wandb locally?
Are you running into this issue when adding tags via the UI? Or programmatically?

hey @freddyheppell, @frederiknolte  - i was able to reproduce this behavior in the UI and have escalated this to our engineering team. will update you as progress arises on the issue, and thanks again for surfacing!

Same issue here, I'm passing in the tags as a list of strings to wandb.init().

@collinmccarthy - which wandb SDK version are you using? if you are logging runs to the same project with the same tags across runs (programmatically), they should appear identical in the UI
could you provide a code snippet for how you're logging these tags? would love to try to investigate this behavior on my end as well

I have the same issue. Using WandbLogger along with pytorch-lightning. The code looks something like this:
logger = WandbLogger(project='mri_uda', group='G', name='N', job_type='train', save_dir=os.environ['HOME'], log_model=True, tags=['my_tag']) trainer = pl.Trainer(logger=logger) trainer.fit(model=model, datamodule=data_module, ckpt_path=ckpt_path)

Bump. I also have this issue when adding tags programmatically.

+1 I added the tags in the UI and I have this issue

Having the same issue using the Python API. It makes tagging much less useful to visually asses different runs in the web UI.

Can we expect any patch soon?

We are addressing this with high priority however, we currently do not have an ETA for a fix. We appreciate your patience and we will keep you posted with any updates.

Hi @freddyheppell @frederiknolte @MaxSchambach @constanzafierro @Karol-G @doronser @collinmccarthy - we have now rolled out a fix for this, and each unique tag will have its own colour in a project 🎉.
We appreciate your patience while we worked on this.


🆕 Software Suggestion | InviZible Pro

Basic Information
Name: InviZible Pro
Category: Android Privacy Addons
URL: https://github.com/Gedsh/InviZible
Description
InviZible Pro is a all-in-one tool that supports DNSCrypt, Tor and Purple I2P, all of which (known as modules) can be run at the same time. It also allows selection of websites and apps that can bypass Tor. There are other advace features like selection of dns servers, various ports, tor bridge, etc. The only requirement is root permission. If root isn't available, DNSCrypt and Tor can be used as proxies with NetGuard or individually with the applications that supports proxy.

Unfortunately, we cannot recommend this app because of its root requirement, its the same reason why we don't recommend AFwall+ and adaway. Rooting is disastrous for your androids security.

Unfortunately, we cannot recommend this app because of its root requirement

Dev is currently looking into a VPN solution. Hopefully this will arrive in a few month.

@blacklight447-ptio: Support for non-root users added in the latest binaries. Take a look here: https://github.com/Gedsh/InviZible/wiki/Proxy-mode-(no-root-required)

How does InviZible Pro configure Tor ports and stream isolation? What part of the code does that?

I strongly recommend to add it, it works surprisingly well, and indeed without the need for root now. It allows to connect to both Tor and I2P networks simultaneously, from any browser. I don't know if other apps than browsers are also tunneled but I would assume so since by default it's the "VPN mode" that is enabled, although it also offers a "Proxy mode" so that we can tunnel per app by setting a proxy (I guess SOCKS5?) per app that supports proxies.

I strongly agree with @lrq3000 as well that InviZible Pro should be added to PrivacyTools. It doesn't require root and can work in both proxy and VPN mode, and allows a combination of Tor, I2P, and DNSCrypt in one package. And it's highly configurable. This is something that is extremely hard to find for Android, which is why I believe it would be a valuable addition.


Enables the mjml renderer to receive a userContext object that is available to all components on rendering

Enables the mjml renderer to receive a userContext object that is available to all components on rendering
We have some components that depend on user data when transforming the MJML code to HTML. Until now, we were using a global variable for context related things, but this can get complicated as we scale up the number of mjml2html concurrent executions.
Usage example:
const html = mjml2html(mjmlContent, {
        userContext: { data },
}).html;

Inside custom components we can fetch it by using:
export default class PAuthQrCode extends BodyComponent {
    render() {
       const context = this.userContext;
       const href = context.data.href;

       return this.renderMJML(`
      <mj-image-customized css-class="logo" align="center" width="175px" height="auto" padding="0" src="${href}?qrcode.png" />
    `);

    }
}

Well that would fall into templating territory and we're against that. Please apply templating before or after rendering (you can use new preprocessors option for that).


handle !

I'm getting errors when I try to use ! commands in notebook cells w/nbprocess, this is because execnb is trying to parse these cells with AST.
This feels a little bit hacky, so opening a PR to get your review.

I think you should strip before you take the first char.

Good catch! I was doing it in the wrong order 😓


Simple test app

Test app for host <--> guest connection

I don't see the .github workflow file (.github/workflows/e2e-tests.yml)

Thanks for that, I added missing file.


Add horizontal and vertical line drawing function.

mvhline and mvvline default to the '─' and '│' respectively.

Thank you @MatthewBennington !


Avconv missing metadata

Avconv video
Av.cli.identify('video.mov')
[AV] Running command: if command -v avprobe 2>/dev/null; then echo "true"; else echo "false"; fi
[AV] Running command: if command -v ffmpeg 2>/dev/null; then echo "true"; else echo "false"; fi
[AV] Found ["avconv", "ffmpeg"], using: Avconv
[AV] Running command: avconv -i "video.mov" 2>&1
=> {:size=>"1920x1080", :aspect=>1.7777777777777777}

FFmpeg video
Av.cli.identify('video.mov')
[AV] Running command: if command -v avprobe 2>/dev/null; then echo "true"; else echo "false"; fi
[AV] Running command: if command -v ffmpeg 2>/dev/null; then echo "true"; else echo "false"; fi
[AV] Found ["ffmpeg"], using: Ffmpeg
[AV] Running command: ffmpeg -i "video.mov" 2>&1
=> {:length=>"0:00:26.73", :fps=>60, :size=>"1920x1080", :aspect=>1.7777777777777777}

Avconv audio
Av.cli.identify('audio.mp3')
[AV] Running command: if command -v avprobe 2>/dev/null; then echo "true"; else echo "false"; fi
[AV] Running command: if command -v ffmpeg 2>/dev/null; then echo "true"; else echo "false"; fi
[AV] Found ["avconv", "ffmpeg"], using: Avconv
[AV] Running command: avconv -i "audio.mp3" 2>&1
=> {:audio_encode=>"mp3", :audio_bitrate=>"44100 Hz", :audio_channels=>"1 channels"}

FFmpeg audio
Av.cli.identify('audio.mp3')
[AV] Running command: if command -v avprobe 2>/dev/null; then echo "true"; else echo "false"; fi
[AV] Running command: if command -v ffmpeg 2>/dev/null; then echo "true"; else echo "false"; fi
[AV] Found ["ffmpeg"], using: Ffmpeg
[AV] Running command: ffmpeg -i "audio.mp3" 2>&1
=> {:length=>"0:00:02.66", :audio_encode=>"mp3", :audio_bitrate=>"44100 Hz", :audio_channels=>"mono"}

Avconv version
avconv version 11.2, Copyright (c) 2000-2014 the Libav developers
  built on Jan 26 2015 11:47:25 with Apple LLVM version 6.0 (clang-600.0.56) (based on LLVM 3.5svn)
Hyper fast Audio and Video encoder

I think that was fixed in #5, no?

no, it's not fixed, i just added some more information to meta.
problem still exists in identify method https://github.com/ruby-av/av/blob/master/lib/av/commands/base.rb#L94

Just updated libav to version 11.3, problem disappeared.
Not gem issue, so some description about version requirements could be added.

Can you confirm the issue on 11.x < 11.3?

With avconv 11.2 gem identify function returns almost nothing about video.
However, avconv command line execution  returns it.
Sent from Nexus 5
On Mar 25, 2015 9:24 PM, "Omar Abdel-Wahab"<EMAIL_ADDRESS>wrote:

Can you confirm the issue on 11.x < 11.3?
—
Reply to this email directly or view it on GitHub
https://github.com/ruby-av/av/issues/3#issuecomment-86181685.


start container with HostConfig was deprecated since v1.10 and removed in v1.12

I can not deploy chaincode to docker v1.12 successfully because HostConfig being passed to client.StartContainer. I see Baohua's comment but i suggest pass a nil to StartContainer because HostConfig has   been passed to  vm.createContainer already.
ref: core/container/dockercontroller/dockercontroller.go

OK, will fix that.

@2016Nishi, FYI

marked.The same error.

[dockercontroller] Start -> ERRO 01e start-could not start container API error (400): {"message":"starting container with HostConfig was deprecated since v1.10 and removed in v1.12"}

I am also getting same error:
[dockercontroller] Start -> ERRO 019 start-could not start container API error (400): {"message":"starting container with HostConfig was deprecated since v1.10 and removed in v1.12"}
[chaincode] Launch -> ERRO 01a launchAndWaitForRegister failed Error starting container: API error (400): {"message":"starting container with HostConfig was deprecated since v1.10 and removed in v1.12"}

@VenkyMadgundi the project has moved to gerrit. This has been fixed there

closing per @muralisrini comment above.


Assetss from wwwroot cannot be found on Docker Image

I have got Linux VM Docker Image up and running but I have encountered one problem (and wasn't able).
All assetss that were in my wwwroot folder cannot be found

Failed to load resource: the server responded with a status of 404 (Not Found)

I have included
 "webroot": "wwwroot"

In project.json file but that doesn't fix the problem. One more thing is that running from VS 2015 (on ISS Express) everything works - is there something that I should include in Dockerfile as well?.
I added VOLUME to docker file but I probably did it wrong because it did not help (to be honest I am not sure how to use it) Dockerfile:
FROM microsoft/aspnet

COPY . /app
WORKDIR /app
RUN ["kpm", "restore"]

VOLUME ["/wwwroot"]

EXPOSE 5004
ENTRYPOINT ["k", "kestrel"]

I am not sure if it's docker issue or asp.

Are you sure that your Dockerfile works at all? The k and kpm commands have been renamed.
It works for me with the latest HelloWeb sample code and the #536 related pull request (see https://github.com/aspnet/Home/pull/537/files). I tested it on MacOSX/boot2docker and opening http://<IP_ADDRESS>:5004/image.jpg works fine. Note that the ip address depends on your setup, of course.
The HelloMvc sample however, does not serve static files from wwwroot. If you want to adjust the HelloWeb sample into serving static files like the HelloMvc sample, then take a look at https://github.com/aspnet/Home/blob/dev/samples/latest/HelloWeb/Startup.cs#L9. You also need to adjust dependencies in project.json to include Microsoft.AspNet.StaticFiles and perhaps also Microsoft.AspNet.Hosting. Not sure about that last one.

I deleted VOLUME ["/wwwroot"] from Dockerfile and instead i try to add Volume usin -v flag in docker run command like so:
docker run -t -v $(pwd)/wwwroot:/wwwroot-d -p 8080:5004 app

but it still gave me nothing. And I am preety sure that Dockerfile works because when I build Image the restore command works.
I did have StaticFiles dependencie but I don't have Hosting - I will add it build, run and tell you if it worked.

Did you manage to load image.jpg from the HelloWeb sample without using docker volumes?

I'm gonna do that first thing tomorrow morning and edit this post to let you know how it went.

Yes, I managed to open image.jpg from HelloWeb sample

Okay that's great, so it seems that what you are dealing with is a docker issue.
I assume that your Dockerfile looks like this:
FROM microsoft/aspnet
COPY . /app
WORKDIR /app
RUN ["dnu", "restore"]
EXPOSE 5004
ENTRYPOINT ["dnx", "project.json", "kestrel"]

Build the docker image:
cd samples/latest/HelloWeb
docker build -t aspnet-home-helloweb .

Create a new mywwwroot directory with a new hello.jpg file and start the docker container:
mkdir mywwwroot
cp wwwroot/image.jpg mywwwroot/hello.jpg
docker run -it -v $(pwd)/mywwwroot:/app/wwwroot -p 5004:5004 aspnet-home-helloweb

Now run this is another terminal window to open the hello.jpg in a browser:
open http://$(boot2docker ip):5004/hello.jpg

or just open http://localhost:5004/hello.jpg if you do not use macosx/boot2docker.
While the docker container is still running you can add a text file to mywwwroot and open it in a browser:
echo "Hello World!" > mywwwroot/foobar.txt
open http://$(boot2docker ip):5004/foobar.txt

You can now add/remove/change files in mywwwroot without having to restart the docker container.

This issue is being closed because it has not been updated in 3 months.
We apologize if this causes any inconvenience. We ask that if you are still encountering this issue, please log a new issue with updated information and we will investigate.


fix: gcp ccm connector no billing export

Describe your changes
Currently we cannot create gcp ccm connectors without a billing export due to a bug where we check for the export on every call:
➜  test tf apply
main.tf

Terraform used the selected providers to generate the following execution plan. Resource actions are
indicated with the following symbols:
  + create

Terraform will perform the following actions:

  # harness_platform_connector_gcp_cloud_cost.example will be created
  + resource "harness_platform_connector_gcp_cloud_cost" "example" {
      + features_enabled      = [
          + "OPTIMIZATION",
          + "VISIBILITY",
        ]
      + gcp_project_id        = "gcp_project_id"
      + id                    = (known after apply)
      + identifier            = "example"
      + name                  = "example"
      + service_account_email =<EMAIL_ADDRESS>    }

Plan: 1 to add, 0 to change, 0 to destroy.

Do you want to perform these actions?
  Terraform will perform the actions described above.
  Only 'yes' will be accepted to approve.

  Enter a value: yes

harness_platform_connector_gcp_cloud_cost.example: Creating...
╷
│ Error: Plugin did not respond
│
│   with harness_platform_connector_gcp_cloud_cost.example,
│   on main.tf line 21, in resource "harness_platform_connector_gcp_cloud_cost" "example":
│   21: resource "harness_platform_connector_gcp_cloud_cost" "example" {
│
│ The plugin encountered an error, and failed to respond to the
│ plugin.(*GRPCProvider).ApplyResourceChange call. The plugin logs may contain more details.
╵

Stack trace from the terraform-provider-harness_v0.23.3 plugin:

panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x2 addr=0x0 pc=0x10388ab0c]

goroutine 7 [running]:
github.com/harness/terraform-provider-harness/internal/service/platform/connector.readConnectorGCPCloudCost(0x103e07908?, 0x140003a8380)
        github.com/harness/terraform-provider-harness/internal/service/platform/connector/gcp_cloud_cost.go:141 +0xdc
github.com/harness/terraform-provider-harness/internal/service/platform/connector.resourceConnectorGCPCloudCostCreateOrUpdate({0x103e07908, 0x14000694ae0}, 0x0?, {0x103cc67e0, 0x140009945c0})
        github.com/harness/terraform-provider-harness/internal/service/platform/connector/gcp_cloud_cost.go:94 +0x64
github.com/hashicorp/terraform-plugin-sdk/v2/helper/schema.(*Resource).create(0x140004fc000, {0x103e07940, 0x1400060e360}, 0xd?, {0x103cc67e0, 0x140009945c0})
        github.com/hashicorp/terraform-plugin-sdk/v2@v2.27.0/helper/schema/resource.go:733 +0xec
github.com/hashicorp/terraform-plugin-sdk/v2/helper/schema.(*Resource).Apply(0x140004fc000, {0x103e07940, 0x1400060e360}, 0x140008e29c0, 0x140008db100, {0x103cc67e0, 0x140009945c0})
        github.com/hashicorp/terraform-plugin-sdk/v2@v2.27.0/helper/schema/resource.go:864 +0x898
github.com/hashicorp/terraform-plugin-sdk/v2/helper/schema.(*GRPCProviderServer).ApplyResourceChange(0x1400000c060, {0x103e07940?, 0x1400060e240?}, 0x14000402910)
        github.com/hashicorp/terraform-plugin-sdk/v2@v2.27.0/helper/schema/grpc_provider.go:1024 +0xb94
github.com/hashicorp/terraform-plugin-go/tfprotov5/tf5server.(*server).ApplyResourceChange(0x140002fa280, {0x103e07940?, 0x140008f3ce0?}, 0x140008d0150)
        github.com/hashicorp/terraform-plugin-go@v0.18.0/tfprotov5/tf5server/server.go:821 +0x3c0
github.com/hashicorp/terraform-plugin-go/tfprotov5/internal/tfplugin5._Provider_ApplyResourceChange_Handler({0x103dad340?, 0x140002fa280}, {0x103e07940, 0x140008f3ce0}, 0x140008d00e0, 0x0)
        github.com/hashicorp/terraform-plugin-go@v0.18.0/tfprotov5/internal/tfplugin5/tfplugin5_grpc.pb.go:422 +0x174
google.golang.org/grpc.(*Server).processUnaryRPC(0x1400044e000, {0x103e0a8e0, 0x14000102d00}, 0x140008e07e0, 0x140000ad710, 0x10447a960, 0x0)
        google.golang.org/grpc@v1.56.2/server.go:1337 +0xc7c
google.golang.org/grpc.(*Server).handleStream(0x1400044e000, {0x103e0a8e0, 0x14000102d00}, 0x140008e07e0, 0x0)
        google.golang.org/grpc@v1.56.2/server.go:1714 +0x840
google.golang.org/grpc.(*Server).serveStreams.func1.1()
        google.golang.org/grpc@v1.56.2/server.go:959 +0x88
created by google.golang.org/grpc.(*Server).serveStreams.func1
        google.golang.org/grpc@v1.56.2/server.go:957 +0x170

Error: The terraform-provider-harness_v0.23.3 plugin crashed!

This is always indicative of a bug within the plugin. It would be immensely
helpful if you could report the crash with the plugin's maintainers so that it
can be fixed. The output above should help diagnose the issue.

By optionally checking for the billing export, only when BILLING is set, we can successfully create gcp ccm connectors without cost connectors:
➜  tttt tf apply
╷
│ Warning: Provider development overrides are in effect
│
│ The following provider development overrides are set in the CLI configuration:
│  - harness/harness in /Users/rileysnyder/git/terraform-provider-harness
│
│ The behavior may therefore not match any released version of the provider and applying changes may
│ cause the state to become incompatible with published releases.
╵

Terraform used the selected providers to generate the following execution plan. Resource actions are
indicated with the following symbols:
  + create

Terraform will perform the following actions:

  # harness_platform_connector_gcp_cloud_cost.gcp will be created
  + resource "harness_platform_connector_gcp_cloud_cost" "gcp" {
      + features_enabled      = [
          + "OPTIMIZATION",
          + "VISIBILITY",
        ]
      + gcp_project_id        = "gcp_project_id"
      + id                    = (known after apply)
      + identifier            = "gcp"
      + name                  = "gcp"
      + service_account_email =<EMAIL_ADDRESS>    }

Plan: 1 to add, 0 to change, 0 to destroy.

Do you want to perform these actions?
  Terraform will perform the actions described above.
  Only 'yes' will be accepted to approve.

  Enter a value: yes

harness_platform_connector_gcp_cloud_cost.gcp: Creating...
harness_platform_connector_gcp_cloud_cost.gcp: Creation complete after 0s [id=gcp]

Apply complete! Resources: 1 added, 0 changed, 0 destroyed.

related to
https://github.com/harness/terraform-provider-harness/pull/617
https://github.com/harness/terraform-provider-harness/pull/617
Comment Triggers

PR Check triggers

Build: trigger build
Sub Category Field Check: trigger subcategoryfieldcheck

trigger build

trigger subcategoryfieldcheck


support for archaea genomes

Hello @iimog ,
I think archaea has a different set of core genes, which we need to specify alone. In the case of gtotree software they separate those 2 cases. It would be nice if there can be such an option in th GUI interface.
Thanks,
Jianshu

bcgTree can work with any set of genes given in a hmm file. In order to use a hmm file other than the default, just provide the path to that file under --hmmfile in "Advanced settings". This way you can use any of the files listed in https://github.com/AstrobioMike/GToTree/blob/master/hmm_sets/hmm-sources-and-info.tsv (you need to manually download them beforehand).


Incorrect PrismaClientKnownRequestError

Bug description
I cannot pass in the following object with the property semanticType set to null or undefined even though in the Prisma Schema, this property is an optional enum:
// Data passed into `prisma.extractionRule.create`
{
  data: {
    semanticType: null,
    id: '9f553af6-a6c1-4245-9c5b-22d6e687e6bf',
  }
}

I receive the following error:
  PrismaClientKnownRequestError3 @PrismaClientKnownRequestError {
    clientVersion: '2.13.0-dev.93',
    code: 'P2011',
    meta: {
      constraint: [
        'semanticType',
      ],
    },
  }

How to reproduce
Look at my schema.
Expected behavior
I can pass in semanticType with the value undefined (or null, not sure which one) into extractionRule.create and I won't get the above error:
Prisma information
Relevant information:
model ExtractionRule {
  id          String    @id
  semanticType SemanticType?
}

enum SemanticType {
    X
    Y
}

Environment & setup

@prisma/cli          : 2.13.0-dev.93
@prisma/client       : 2.13.0-dev.93
Current platform     : debian-openssl-1.1.x
Query Engine         : query-engine c497f3b49d089965e74485c540eb84ef0fbbcf0d (at<EMAIL_ADDRESS>Migration Engine     : migration-engine-cli c497f3b49d089965e74485c540eb84ef0fbbcf0d (at<EMAIL_ADDRESS>Introspection Engine : introspection-core c497f3b49d089965e74485c540eb84ef0fbbcf0d (at<EMAIL_ADDRESS>Format Binary        : prisma-fmt c497f3b49d089965e74485c540eb84ef0fbbcf0d (at<EMAIL_ADDRESS>Studio               : 0.327.0

I am unable to reproduce this with 2.13.0-dev.98.

Please try again with the latest version and if you can still reproduce this, please share a reproduction inside of a git repo.

I can't reproduce -- most likely this is an error on my side. I'll re-open this if I can create a reproduction with a git repository.