Error correction algorithm of the linear code

error_correction.jl

using DataStructures


function int_to_binarray(number, array_length)
    """
    Convert the given number into a fixed length binary array
    """
    binstring = bin(number)

    # padding for alignment of the lengths of vectors
    padding_length = array_length-length(binstring)
    padding = zeros(Int, 1, padding_length)

    r = map(x -> parse(Int, x), collect(binstring))  # bin to int array

    r = hcat(padding, r')  # r is a row vector
end


hamming_weight(x) = sum(x)


function coset_leader(vectors)
    """
    Return a vector which has the smallest hamming weight.
    This vector is called coset leader.
    """
    weights = map(hamming_weight, vectors)
    index = indmin(weights)
    vectors[index]
end


function parity_check_matrix(G)
    """Generate a Parity-check matrix from a generator matrix `G`"""
    P = G[:, size(G, 1)+1:end]
    H = hcat(P', eye(size(P, 2)))
end


syndrome(r, H) = convert(Array{Int}, r*H' % 2)


function standard_array(G)
    """
    Generate a map from syndrome to coset leader from a generator matrix `G`.
    """

    H = parity_check_matrix(G)
    # maps syndrome to coset
    n = size(G, 2)
    stdarray = DefaultDict(Array, Array, ones(Int, 1, n))
    for i in 0:2^n-1  # iterate over all elements in F₂ⁿ
        r = int_to_binarray(i, n)
        s = syndrome(r, H)
        if hamming_weight(r) < hamming_weight(stdarray[s])
            stdarray[s] = r
        end
    end
    return stdarray
end


G = [
    1 0 1 1 0 0;
    0 1 1 0 1 0;
]

println("Standard array")

stdarray = standard_array(G)

println("syndrome  | coset leader")
for s in keys(stdarray)
    println("$s | $(stdarray[s])")
end
println("")

println("Error correction")

r = [1 1 1 1 1 0]
H = parity_check_matrix(G)
s = syndrome(r, H)
println("r = $r")
println("s = r*H' = $s")
println("e = $(stdarray[s])")
println("r - e = $(r-stdarray[s])")

result.txt

Standard array
syndrome  | coset leader
[1 0 0 0] | [0 0 1 0 0 0]
[1 1 0 1] | [1 0 0 0 0 1]
[1 0 1 1] | [0 1 0 0 0 1]
[0 0 0 1] | [0 0 0 0 0 1]
[1 1 1 0] | [0 1 0 1 0 0]
[1 0 1 0] | [0 1 0 0 0 0]
[1 1 0 0] | [1 0 0 0 0 0]
[1 1 1 1] | [0 1 0 1 0 1]
[0 0 1 1] | [0 0 0 0 1 1]
[1 0 0 1] | [0 0 1 0 0 1]
[0 1 1 0] | [0 0 0 1 1 0]
[0 1 1 1] | [0 0 0 1 1 1]
[0 0 1 0] | [0 0 0 0 1 0]
[0 0 0 0] | [0 0 0 0 0 0]
[0 1 0 0] | [0 0 0 1 0 0]
[0 1 0 1] | [0 0 0 1 0 1]

Error correction
r = [1 1 1 1 1 0]
s = r*H' = [1 0 0 0]
e = [0 0 1 0 0 0]
r - e = [1 1 0 1 1 0]