Editing Hamming code (section)

===General algorithm===
The following general algorithm generates a single-error correcting (SEC) code for any number of bits. The main idea is to choose the error-correcting bits such that the index-XOR (the [[XOR]] of all the bit positions containing a 1) is 0. We use positions 1, 10, 100, etc. (in binary) as the error-correcting bits, which guarantees it is possible to set the error-correcting bits so that the index-XOR of the whole message is 0. If the receiver receives a string with index-XOR 0, they can conclude there were no corruptions, and otherwise, the index-XOR indicates the index of the corrupted bit.

An algorithm can be deduced from the following description:

# Number the bits starting from 1: bit 1, 2, 3, 4, 5, 6, 7, etc.
# Write the bit numbers in binary:  1, 10, 11, 100, 101, 110, 111, etc.
# All bit positions that are powers of two (have a single 1 bit in the binary form of their position) are parity bits: 1, 2, 4, 8, etc. (1, 10, 100, 1000)
# All other bit positions, with two or more 1 bits in the binary form of their position, are data bits.
# Each data bit is included in a unique set of 2 or more parity bits, as determined by the binary form of its bit position.
## Parity bit 1 covers all bit positions which have the '''least''' significant bit set: bit 1 (the parity bit itself), 3, 5, 7, 9, etc.
## Parity bit 2 covers all bit positions which have the '''second''' least significant bit set: bits 2–3, 6–7, 10–11, etc.
## Parity bit 4 covers all bit positions which have the '''third''' least significant bit set: bits 4–7, 12–15, 20–23, etc.
## Parity bit 8 covers all bit positions which have the '''fourth''' least significant bit set: bits 8–15, 24–31, 40–47, etc.
## In general each parity bit covers all bits where the bitwise AND of the parity position and the bit position is non-zero.

If a byte of data to be encoded is 10011010, then the data word (using _ to represent the parity bits) would be __1_001_1010, and the code word is 011100101010.

The choice of the parity, even or odd, is irrelevant but the same choice must be used for both encoding and decoding.

This general rule can be shown visually:

:{| class="wikitable" style="text-align:center;"
|-
!colspan="2"| <span style="color:#888">Bit position</span>
! <span style="color:#888">1</span> !! <span style="color:#888">2</span> !! <span style="color:#888">3</span> !! <span style="color:#888">4</span> !! <span style="color:#888">5</span> !! <span style="color:#888">6</span> !! <span style="color:#888">7</span> !! <span style="color:#888">8</span> !! <span style="color:#888">9</span> !! <span style="color:#888">10</span> !! <span style="color:#888">11</span> !! <span style="color:#888">12</span> !! <span style="color:#888">13</span> !! <span style="color:#888">14</span> !! <span style="color:#888">15</span> !! <span style="color:#888">16</span> !! <span style="color:#888">17</span> !! <span style="color:#888">18</span> !! <span style="color:#888">19</span> !! <span style="color:#888">20</span>
|rowspan="7"| ...
|-
!colspan="2"| Encoded data bits
!style="background-color: #90FF90;"| p1
!style="background-color: #90FF90;"| p2 !! d1
!style="background-color: #90FF90;"| p4 !! d2 !! d3 !! d4
!style="background-color: #90FF90;"| p8 !! d5 !! d6 !! d7 !! d8 !! d9 !! d10 !! d11
!style="background-color: #90FF90;"| p16 !! d12 !! d13 !! d14 !! d15
|-
!rowspan="5"|Parity<br />bit<br />coverage
!style="background-color: #90FF90;"| p1
| {{ya}} ||   || {{ya}} ||   || {{ya}} ||   || {{ya}} ||   || {{ya}} ||   || {{ya}} ||   || {{ya}} ||   || {{ya}} ||   || {{ya}} ||   || {{ya}} || 
|-
!style="background-color: #90FF90;"| p2
|   || {{ya}} || {{ya}} ||   ||   || {{ya}} || {{ya}} ||   ||   || {{ya}} || {{ya}} ||   ||   || {{ya}} || {{ya}} ||   ||   || {{ya}} || {{ya}} || 
|-
!style="background-color: #90FF90;"| p4
|   ||   ||   || {{ya}} || {{ya}} || {{ya}} || {{ya}} ||   ||   ||   ||   || {{ya}} || {{ya}} || {{ya}} || {{ya}} ||   ||   ||   ||   || {{ya}}
|-
!style="background-color: #90FF90;"| p8
|   ||   ||   ||   ||   ||   ||   || {{ya}} || {{ya}} || {{ya}} || {{ya}} || {{ya}} || {{ya}} || {{ya}} || {{ya}} ||   ||   ||   ||   || 
|-
!style="background-color: #90FF90;"| p16
|   ||   ||   ||   ||   ||   ||   ||   ||   ||   ||   ||   ||   ||   ||   || {{ya}} || {{ya}} || {{ya}} || {{ya}} || {{ya}}
|}

Shown are only 20 encoded bits (5 parity, 15 data) but the pattern continues indefinitely.  The key thing about Hamming codes that can be seen from visual inspection is that any given bit is included in a unique set of parity bits.  To check for errors, check all of the parity bits.  The pattern of errors, called the [[error syndrome]], identifies the bit in error.  If all parity bits are correct, there is no error.  Otherwise, the sum of the positions of the erroneous parity bits identifies the erroneous bit.  For example, if the parity bits in positions 1, 2 and 8 indicate an error, then bit 1+2+8=11 is in error.  If only one parity bit indicates an error, the parity bit itself is in error.

With {{mvar|m}} parity bits, bits from 1 up to <math>2^m-1</math> can be covered. After discounting the parity bits, <math>2^m-m-1</math> bits remain for use as data. As {{mvar|m}} varies, we get all the possible Hamming codes:

{| class="wikitable" style="text-align:right"
|-
! Parity bits !! [[Block code#The block length n|Total bits]] !! [[Block code#The message length k|Data bits]] !! Name !! [[Block code#The rate R|Rate]]
|-
| 2 || 3 || 1|| Hamming(3,1)<br/>(Triple [[repetition code]]) || 1/3 ≈ 0.333
|-
| 3 || 7 || 4 || [[Hamming(7,4)]] || 4/7 ≈ 0.571
|-
| 4 || 15 || 11 || Hamming(15,11) || 11/15 ≈ 0.733
|-
| 5 || 31 || 26 ||Hamming(31,26) || 26/31 ≈ 0.839
|-
| 6 || 63 || 57 ||Hamming(63,57) || 57/63 ≈ 0.905
|-
| 7 || 127 || 120 ||Hamming(127,120) || 120/127 ≈ 0.945
|-
| 8 || 255 || 247 ||Hamming(255,247) || 247/255 ≈ 0.969
|-
| 9 || 511 || 502 ||Hamming(511,502) ||502/511 ≈ 0.982
|-
| colspan="5" | ...
|-
|{{mvar|m}}
|<math>n=2^m-1</math>
|<math>k=2^m-m-1</math>
|Hamming<math>(2^m-1,2^m-m-1)</math>
|<math>(2^m - m - 1)/(2^m-1)</math>
|}