Skip to content

Instantly share code, notes, and snippets.

@IshitaTakeshi
Last active December 4, 2016 14:44
Show Gist options
  • Save IshitaTakeshi/409cc5b13e34d574dfa5017db7613c0e to your computer and use it in GitHub Desktop.
Save IshitaTakeshi/409cc5b13e34d574dfa5017db7613c0e to your computer and use it in GitHub Desktop.
Error correction algorithm of the linear code
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])")
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]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment