System and method having optimal, systematic
A computer-implemented method and computer program product comprising optimal, systematic q-ary codes for correcting all asymmetric and symmetric errors of limited magnitude are provided.
1. A computer-implemented method for systematic decoding of an information vector for use in correction of all asymmetric errors of maximum magnitude l and executed by a processor, comprising:
a) providing a q-ary encoded vector that includes an information vector having k received information digits, (x′ k-1 , x′ k-2 , . . . , x′ 0 ) and having received check symbols (c′ r-1 , c′ r-2 , . . . , c′ 0 ), where
r
≥
k
×
log
(
l
+
1
)
log
⌈
q
l
+
1
⌉
;
b) recovering the check symbols (c r-1 , c r-2 , . . . , c 0 ) by rounding each received check symbol which is not a multiple of (l+1) upwards to the nearest multiple of (l+1);
c) computing a, the value of
(
c
r
-
1
l
+
1
,
c
r
-
2
l
+
1
,
…
,
c
0
l
+
1
)
as a vector over
Z
⌈
q
l
+
1
⌉
as
a
=
(
c
r
-
1
l
+
1
)
⌈
q
l
+
1
⌉
r
-
1
+
(
c
r
-
2
l
+
1
)
⌈
q
l
+
1
⌉
r
-
2
+
…
+
(
c
0
l
+
1
)
⌈
q
l
+
1
⌉
0
;
d) representing a in radix (l+1) number with k digits as y=(y k-1 ,y k-2 , . . . ,y 0 );
e) computing e i =(y i −x′ i ) mod(l+1); and
f) computing the corrected codeword, (x k-1 , x k-2 , . . . , x 0 ), as x i =x′ i +e i , where i=0, 1, . . . , k-1.
2. The method according to claim 1 , wherein
r
=
⌈
k
×
log
(
l
+
1
)
log
⌈
q
l
+
1
⌉
⌉
.
3. A computer program product, comprising a non-transitory computer-readable medium having a computer readable program code embodied therein, said computer readable program code adapted to be executed to implement a method for decoding an information vector for use in systematic correction of all asymmetric errors of maximum magnitude, l, comprising:
a) providing a q-ary encoded vector that includes an information vector having k received information digits, (x′ k-1 , x′ k-2 , . . . , x′ 0 ) and having received check symbols (c′ r-1 , c′ r-2 , . . . , c′ 0 ), where
r
≥
k
×
log
(
l
+
1
)
log
⌈
q
l
+
1
⌉
;
b) recovering the check symbols (c r-1 , c r-2 , . . . , c 0 ) by rounding each received check symbol which is not a multiple of (l+1) upwards to the nearest multiple of (l+1);
c) computing a, the value of
(
c
r
-
1
l
+
1
,
c
r
-
2
l
+
1
,
…
,
c
0
l
+
1
)
as a vector over
Z
⌈
q
l
+
1
⌉
as
a
=
(
c
r
-
1
l
+
1
)
⌈
q
l
+
1
⌉
r
-
1
+
(
c
r
-
2
l
+
1
)
⌈
q
l
+
1
⌉
r
-
2
+
…
+
(
c
0
l
+
1
)
⌈
q
l
+
1
⌉
0
;
d) representing a in radix (l+1) number with k digits as y=(y k-1 ,y k-2 , . . . ,y 0 );
e) computing e i =(y i −x′ i ) mod(l+1); and
f) computing the corrected codeword, (x k-1 , x k-2 , . . . , x 0 ), as x i =x′ i +e i , where i=0, 1, . . . , k-1.
4. The computer program product according to claim 3 , wherein
r
=
⌈
k
×
log
(
l
+
1
)
log
⌈
q
l
+
1
⌉
⌉
.
5. A computer-implemented method for systematic decoding of an information vector for use in correction of all symmetric errors of maximum magnitude l and executed by a processor, comprising:
a) providing a q-ary encoded vector that includes an information vector having k received information digits, (x′ k-1 , x′ k-2 , . . . , x′ 0 ) and having received check symbols (c′ r-1 , c′ r-2 , . . . , c′ 0 ), where
r
≥
k
×
log
(
2
l
+
1
)
log
⌈
q
2
l
+
1
⌉
;
b) recovering the check symbols by rounding each received check symbol (c r-1 , c r-2 , . . . , c 0 ) which is not a multiple of (2l+1) either upwards or downwards to the nearest multiple of (2l+1), whichever is closer;
c) computing a, the value of
(
c
r
-
1
2
l
+
1
,
c
r
-
2
2
l
+
1
,
…
,
c
0
2
l
+
1
)
as a vector over
Z
⌈
q
2
l
+
1
⌉
as
a
=
(
c
r
-
1
2
l
+
1
)
⌈
q
2
l
+
1
⌉
r
-
1
+
(
c
r
-
2
2
l
+
1
)
⌈
q
2
l
+
1
⌉
r
-
2
+
…
+
(
c
0
2
l
+
1
)
⌈
q
2
l
+
1
⌉
0
;
d) representing a in radix (2l+1) number with k digits as y=(y k-1 ,y k-2 , . . . ,y 0 );
e) computing e i =(y i −x′ i )mod(2l+1) such that −l≦e i ≦l; and
f) computing the corrected codeword, (x k-1 , x k-2 , . . . , x 0 ), as x i =x′ i +e i , where i=0, 1, . . . , k-1.
6. The method according to claim 5 , wherein
r
=
k
×
log
(
2
l
+
1
)
log
⌈
q
2
l
+
1
⌉
.
7. A computer program product, comprising a non-transitory computer-readable medium having a computer readable program code embodied therein, said computer readable program code adapted to be executed to implement a method for decoding an information vector for use in systematic correction of all symmetric errors of maximum magnitude, l, comprising:
a) providing a q-ary encoded vector that includes an information vector having k received information digits, (x′ k-1 , x′ k-2 , . . . , x′ 0 ) and having received check symbols (c′ r-1 , c′ r-2 , . . . , c′ 0 ), where
r
≥
k
×
log
(
2
l
+
1
)
log
⌈
q
2
l
+
1
⌉
;
b) recovering the check symbols (c r-1 , c r-2 , . . . , c 0 ) by rounding each received check symbol which is not a multiple of (2l+1) either upwards or downwards to the nearest multiple of (2l+1), whichever is closer;
c) computing a, the value of
(
c
r
-
1
2
l
+
1
,
c
r
-
2
2
l
+
1
,
…
,
c
0
2
l
+
1
)
as a vector over
Z
⌈
q
2
l
+
1
⌉
as
a
=
(
c
r
-
1
2
l
+
1
)
⌈
q
2
l
+
1
⌉
r
-
1
+
(
c
r
-
2
2
l
+
1
)
⌈
q
2
l
+
1
⌉
r
-
2
+
…
+
(
c
0
2
l
+
1
)
⌈
q
2
l
+
1
⌉
0
;
d) representing a in radix (2l+1) number with k digits as y=(y k-1 ,y k-2 , . . . ,y 0 );
e) computing e i =(y i −x′ i )mod(2l+1) such that −l≦e i ≦l; and
computing the corrected codeword, (x k-1 , x k-2 , . . . , x 0 ), as x i =x′ i +e i , where i=0, 1, . . . , k-1.
8. The computer program product according to claim 7 , wherein
r
=
k
×
log
(
2
l
+
1
)
log
⌈
q
2
l
+
1
⌉
.