Given a stream of bits, output the shortest possible Hamming code that encodes it.

The steps to generate the Hamming code are as follows, although your submission does not necessarily have to conform to them as long as it produces identical output. The input 110100101 will be used as an example.

  1. Pad the input with trailing zeroes until its length is 2m - m - 1 for some integer m.

    110100101        becomes
  2. Insert spaces at every position with an index of 2i (note that all indexing is 1-based for the purposes of this algorithm). This will insert m spaces for parity bits, resulting in 2m - 1 bits total.

    11010010100      becomes
  3. Fill in the parity bits. A parity bit at index i is calculated by taking the sum modulo 2 of all bits whose index j satisfies i & j ≠ 0 (where & is bitwise AND). Note that this never includes other parity bits.

    __1_101_0010100  becomes

Input may be taken as a list (or a string) of any two distinct elements, which do not necessarily have to be 0 and 1. Output must be in an identical format. (Input or output as an integer with the corresponding binary representation is disallowed, as this format cannot express leading 0s.)

The input will always have a length of at least 1.

Test cases (of the form input output):

0 000
1 111
01 1001100
1011 0110011
10101 001101011000000
110100101 111110100010100
00101111011 110001001111011
10100001001010001101 0011010100010010010001101000000
  • \$\begingroup\$ What significance does the padding have? \$\endgroup\$ – Neil May 28 '17 at 20:22

JavaScript (ES6), 116 bytes


If the padding is unnecessary, then for 97 bytes:

| improve this answer | |

Mathematica, 332 bytes


Try it online : copy and paste code using ctrl+v, place input at the end of the code and hit shift+enter to run
(Wolfram-cloud will print "x" between digits but this doesn't happen in mathimatica)









| improve this answer | |

APL (Dyalog Unicode), 64 bytes

{u∨(~k)\⌽m≠.∧u←(⍵↑⍨g l)\⍨k←1<1⊥m←2⊥⍣¯1⍳¯1+2*l←⌈(g←2∘*-+∘1)⍣¯1≢⍵}

Try it online!

A dfn that takes a boolean vector as its right argument.

Ungolfed with comments

  g←2∘*-+∘1  ⍝ A function that gives the data size from parity size; 2^x - (x+1)
  l←⌈g⍣¯1≢⍵  ⍝ Parity size from input length by inverting(⍣¯1) g
  m←2⊥⍣¯1⍳¯1+2*l  ⍝ Column matrix of bit patterns of 1..2^l-1
  k←1<1⊥m  ⍝ A boolean mask indicating where the data bits should go
  u←(⍵↑⍨g l)\⍨k  ⍝ Data pattern moved into appropriate positions:
     ⍵↑⍨g l      ⍝ Overtake ⍵ by length (g l)
            \⍨k  ⍝ Move the bits to the positions of 1 bits of k
  u∨(~k)\⌽m≠.∧u  ⍝ Complete the codeword:
          m≠.∧u  ⍝ Compute the parity (data AND each row of m, then reduce by XOR)
         ⌽       ⍝ Reverse so that LSB goes first
    (~k)\        ⍝ Fill in the parity positions with parity bits
  u∨             ⍝ Combine with data bits
| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.