Also known as (7,4) code,7 trainsmitted bits for 4 source code.
TRANSMIT
The transmitted procedure can be reprecented as follows.
$t=G^Ts$
where G is:
import numpy as np
G = np.matrix(
[[1,0,0,0],
[0,1,0,0],
[0,0,1,0],
[0,0,0,1],
[1,1,1,0],
[0,1,1,1],
[1,0,1,1]]).T
s=np.matrix([[1,1,1,0]]).T t = (G.T*s)%2
visualization
$t_5,t_6,t_7$ is called parity-check bits
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
DECODING
1.intuitive way: measure the similarity between the recieved bits $r$ and the encoded codes $t$
2.Syndrome decoding
dashed line for which parity is not even(unhappy)
full line for which parity is even(happy)
find the unique bit,that lies inside all unhappy circles and outside all happy circles
the corresponding syndrome z as follow:
(b) 110 ($t_5$ not even,$t_6$ not even,$t_7$ even),$r_2$ should be unflipped
(c) 100 ($t_5$ not even,$t_6$ even,$t_7$ even),$r_5$ should be unflipped
(d) 111 ($t_5$ not even,$t_6$ not even,$t_7$ not even),$r_3$ should be unflipped
all the situations is listed in table below:
the syndrome z can be achieved by matrix:
$z=Hr$
which H is:
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
PERFORMANCE
1.when there is only one bit flipped in all 7 bits,the decoder can always get right
2.when there are more than one bits flippend,the decoder get wrong
the single bit error rate，can be estimate as follow：
$p_b \approx \frac{1-{(1-f)}^2-7{(1-f)}^6f}{2}$
the exact error rate is about 0.6688,which can be computed with following program.
import numpy as np
import copy
import itertools
from scipy.misc import comb def encode(s):
G = np.array(
[[1,0,0,0],
[0,1,0,0],
[0,0,1,0],
[0,0,0,1],
[1,1,1,0],
[0,1,1,1],
[1,0,1,1]]
) return np.dot(G,s)%2 def decode(r):
t_hat = copy.deepcopy(r)
H = np.array(
[[1,1,1,0,1,0,0],
[0,1,1,1,0,1,0],
[1,0,1,1,0,0,1]]
) syndrome_map = {0:-1,
1:6,
10:5,
11:3,
100:4,
101:0,
110:1,
111:2} syndrome = np.dot(np.dot(H,r)%2,np.array([100,10,1]))
if syndrome_map[syndrome]>=0:
t_hat[syndrome_map[syndrome]] = (t_hat[syndrome_map[syndrome]]+1)%2 return t_hat def flipn(flip_list,t):
'''
flipped the bits specified by flip_list and return it
:param flip_list:
:param t:
:return:
'''
r = copy.deepcopy(t)
for flip in flip_list:
r[flip] = (r[flip]+1)%2
return r def flipn_avg_err(n,s):
'''
get the average error bits when flip n bits
:param n:
:param s:
:return:
'''
t = encode(s)
items = range(7)
errors = 0
count = 0
for flip in itertools.combinations(items,n):
r = flipn(list(flip),t)
t_hat = decode(r) errors += 4-sum(s==t_hat[:4])
count += 1
return errors*1.0/count f = 0.9
s = np.array([0,0,0,0])
all_error = 0.0
for n in range(2,8):
error = flipn_avg_err(n,s)
all_error += error*comb(7,n)*(f**(7-n))*((1-f)**n)
print all_error/4
python