Generate Hamming codes

Question

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 2^m - m - 1 for some integer m.

   110100101        becomes
   11010010100
   

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

   11010010100      becomes
   __1_101_0010100
   

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
   111110100010100
   

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

Answer 1

JavaScript (ES6), 116 bytes

f=(a,p=i=0)=>1/a[p]?f(a,p+p+1,a.splice(p,0,0)):[...Array(p)].map(_=>i&++i?~~a[i-1]:a.reduce((p,e,j)=>p^=++j&i&&e,0))

If the padding is unnecessary, then for 97 bytes:

f=(a,p=i=0)=>1/a[p]?f(a,p+p+1,a.splice(p,0,0)):a.map(e=>i&++i?e:a.reduce((p,e,j)=>p^=++j&i&&e,0))

Answer 2

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

f←{
  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
}

Answer 3

Mathematica, 332 bytes

R[n_,m_]:=Module[{a,l,i},i=n;If[i==0,a={0},a={};While[i>0,If[IntegerQ[i/2],PrependTo[a,0];i/=2,PrependTo[a,1];i=(i-1)/2]]];l=Length[a];Do[PrependTo[a,0],{i,m-l}];a];F[m_]:=Transpose@Table[R[i,m],{i,2^m-1}];F[m_,K_]:=Module[{Z,i,N,Y},Z=F[m];N=NullSpace[Z,Modulus->2];Y=Mod[R[email protected],2]];Row@F[#,PadRight[IntegerDigits@#2,2^#-1-#]]&

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)

Input

[4,10101]

Output

001101011000000

Input

[5,10100001001010001101]

Output

0011010100010010010001101000000