This was a twist on Longtitudinal Redundancy Check (LRC) [ref]. I thought the concept was interesting and wondered what would happen if one expanded it into a multi-dimensional system. The idea culminates in an ability to find an intersection of parity errors but also exhibits some quirky behavior for specific bit flips and combinations of flips. My implementation computes the multi-dimensional parity as a inhomogenous array part to the actual data since trying to make a perfect square, cube, or whatever with the parity and data leads to unused bit positions. I compute the parity independently in that case and figured it would be best if the parity went through a post-coder that interleaved it with the actual data and then on decoding deinterleaved.
I’ve done some rough preliminary testing but nothing substantial and a comparative analysis with other error correction schemes is needed but it does appear to work at least somewhat.
def ec2d_read_syndrome(dims, pa, pb):
"""If ec2d_encode is called on received data then
pass that as `pa` or `pb` and then pass the parity
data received as the other. This will identify bit
error positions if correctable or identify if there
is some unknown error.
"""
dims = np.array(dims)
#print('-- calculating edges --')
edge_vectors = []
edge_axis = []
edge_dim = []
for x in range(len(dims)):
edge_vector = [0] * len(dims)
edge_vector[x] = 1
edge_vectors.append(np.array(edge_vector))
#print('edge_vector', edge_vector)
ea = []
ed = []
for y in range(len(dims)):
ev = [0] * len(dims)
if y != x:
ev[y] = 1
#print('ev', ev)
ea.append(np.array(ev))
ed.append(y)
edge_dim.append(ed)
edge_axis.append(ea)
edge_vector = None
pndx = 0
suspect = {}
bad = set()
for edge_ndx in range(len(edge_axis)):
#print('---edge---')
# Iterate the parity edge by setting the initial position
# to maximum of the vector then incrementing each axis that
# isn't the vector axis until all edge positions have been
# iterated.
ead = edge_dim[edge_ndx]
ea = edge_axis[edge_ndx]
pos = np.array([0] * len(dims))
pos = np.zeros(len(dims), np.int64)
#pos += ((edge_vectors[edge_ndx] + 1) % 2) * (dims_n - 1)
while True:
# On each iteration we take on a new edge position. Each edge
# position holds a parity bit. Using the edge vector we can
# move through all the data bits that make up the parity.
#print(' compute', pos)
if pa[pndx] != pb[pndx]:
d_pos = pos.copy()
for x in range(0, dims[edge_ndx]):
d_pos[edge_ndx] = x
#print(' d_pos', d_pos)
_d_pos = tuple(d_pos)
if _d_pos in suspect:
suspect[_d_pos] += 1
if suspect[_d_pos] >= 3:
bad.add(_d_pos)
else:
suspect[_d_pos] = 1
#sum += data[tuple(d_pos)]
#if sum & 1 == 1:
# data2.append(1)
#else:
# data2.append(0)
pndx += 1
ea_ndx = 0
while True:
# Advance the edge position (through all edge positions).
pos += ea[ea_ndx]
if np.sum(ea[ea_ndx] * pos) == dims[ead[ea_ndx]]:
# Reached max position on this axis. Clear the position place.
ea_clear = (ea[ea_ndx] + 1) % 2
pos *= ea_clear
ea_ndx += 1
if ea_ndx == len(dims) - 1:
break
else:
break
if ea_ndx == len(dims) - 1:
break
return bad
def ec2d_encode(data, dims):
"""Given binary data as a list and the dimensions of
the ec2d encode return the parity data. This is only
the parity data and does not contain the data. The
data and parity should be combined or interleaved.
"""
tc = 1
for dim in dims:
tc = tc * dim
dims = np.array(dims)
assert tc == len(data)
# 2 dims... 2 edges - each edge 1d
# [1, 0]
# [0, 1]
# 3 dims... 3 edges - each edge 2d
# [1, 0, 0]
# [0, 1, 0]
# [0, 0, 1]
# 4 dims... 4 edges - each edge 3d
# Shape the input and output data. The output should be +1
# on all dimensions. Then copy the input data into the
# output.
data = np.array(data)
data = data.reshape(dims)
data2 = []
edge_vectors = []
edge_axis = []
edge_dim = []
#print('-- calculating edges --')
for x in range(len(dims)):
edge_vector = [0] * len(dims)
edge_vector[x] = 1
edge_vectors.append(np.array(edge_vector))
#print('edge_vector', edge_vector)
ea = []
ed = []
for y in range(len(dims)):
ev = [0] * len(dims)
if y != x:
ev[y] = 1
#print('ev', ev)
ea.append(np.array(ev))
ed.append(y)
edge_dim.append(ed)
edge_axis.append(ea)
#print('--compute section--')
edge_vector = None
for edge_ndx in range(len(edge_axis)):
#print('---edge---')
# Iterate the parity edge by setting the initial position
# to maximum of the vector then incrementing each axis that
# isn't the vector axis until all edge positions have been
# iterated.
ead = edge_dim[edge_ndx]
ea = edge_axis[edge_ndx]
pos = np.array([0] * len(dims))
pos = np.zeros(len(dims), np.int64)
#pos += ((edge_vectors[edge_ndx] + 1) % 2) * (dims_n - 1)
while True:
# On each iteration we take on a new edge position. Each edge
# position holds a parity bit. Using the edge vector we can
# move through all the data bits that make up the parity.
#print('compute', pos)
d_pos = pos.copy()
sum = 0
for x in range(0, dims[edge_ndx]):
d_pos[edge_ndx] = x
sum += data[tuple(d_pos)]
if sum & 1 == 1:
data2.append(1)
else:
data2.append(0)
ea_ndx = 0
while True:
# Advance the edge position (through all edge positions).
pos += ea[ea_ndx]
if np.sum(ea[ea_ndx] * pos) == dims[ead[ea_ndx]]:
# Reached max position on this axis. Clear the position place.
ea_clear = (ea[ea_ndx] + 1) % 2
pos *= ea_clear
ea_ndx += 1
if ea_ndx == len(dims) - 1:
break
else:
break
if ea_ndx == len(dims) - 1:
break
return data2