System and method having optimal, systematic q-ary codes for correcting all asymmetric and symmetric errors of limited magnitude
View Patent ↗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 encoding 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 information vector having k information digits, (x k-1 ,x k-2 , . . . ,x 0 );
b) computing a, the value of (x k-1 ,x k-2 , . . . ,x 0 ) mod (l+1) as a vector over (l+1) according to the formula
a=y k-1 ( l+ 1) k-1 +y k-2 ( l+ 1) k-2 +. . . +y 0 ( l+ 1) 0 , where
y i = x i mod( l+ 1), iε{ 0,1, . . . , k− 1};
c) representing a in radix
⌈
q
l
+
1
⌉
number with r digits: (a r-1 ,a r-2 , . . . ,a 0 ),
where
r
≥
k
×
log
(
l
+
1
)
log
⌈
q
l
+
1
⌉
;
d) computing the check part, c, according to the formula c=(c r-1 ,c r-2 , . . . ,c 0 ), where c i =(l+1)a i ,∀iε{0,1, . . . , r−1}; and
e) outputting an encoded vector that includes the information digits and check part, wherein any two check parts computed according to step (d) are at least l+1 apart.
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 encoding an information vector for use in systematic correction of all asymmetric errors of maximum magnitude /comprising:A=πr 2
a) providing a q-ary information vector having k information digits, (x k-1 ,x k-2 , . . . ,x 0 );
b) computing a , the value of (x k-1 ,x k-2 , . . . ,x 0 ) mod (l+1) as a vector over (l+1) according to the formula
a=y k-1 ( l+ 1) k-1 +y k-2 ( l+ 1) k-2 +. . . +y 0 ( l+ 1) 0 , where
y i = x i mod( l+ 1), iε{ 0,1, . . . , k− 1};
c) representing a in radix
⌈
q
l
+
1
⌉
number with r digits: (a r-1 ,a r-2 , . . . ,a 0 ), where
r
≥
k
×
log
(
l
+
1
)
log
⌈
q
l
+
1
⌉
;
d) computing the check part, c, according to the formula c=(c r-1 ,c r-2 , . . . ,c 0 ), where c i =(l+1)a i ,∀iε{0,1, . . . ,r−1}; and
e) outputting an encoded vector that includes the information digits and check part, wherein any two check parts computed according to step (d) are at least l+1 apart.
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 asymmetric errors of maximum magnitude / 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
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, wherein any two of the check symbols are at least l+1 apart.
6. The method according to claim 5 , wherein
r
=
⌈
k
×
log
(
l
+
1
)
log
⌈
q
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 asymmetric errors of maximum magnitude /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 +e i , where i=0,1, . . . ,k−1, wherein any two of the check symbols are at least l+1 apart.
8. The computer program product according to claim 7 , wherein
r
=
⌈
k
×
log
(
l
+
1
)
log
⌈
q
l
+
1
⌉
⌉
.
9. A computer-implemented method for systematic encoding of an information vector for use in correction of all symmetric errors of maximum magnitude / and executed by a processor, comprising:
a) providing a q-ary information vector having k information digits, (x k-1 ,x k-2 , . . . ,x 0 );
b) computing a , the value of (x k-1 ,x k-2 , . . . ,x 0 )mod(2l+1) as a vector over (2l+1) according to the formula
a=y k-1 (2 l +1) k-1 +y k-2 (2 l +1) k-2 +. . .+ y 0 (2 l +1) 0 ,
where y i =x i mod(2l+1),iε{0,1, . . . ,k−1};
c) representing a in radix
⌈
q
2
l
+
1
⌉
number with r digits, (a r-1 ,a r-2 , . . . ,a 0 ),
where
r
≥
k
×
log
(
2
l
+
1
)
log
⌈
q
2
l
+
1
⌉
;
d) computing the check part as c =(c r-1 ,c r-2 , . . . ,c 0 ),
where c i =(2l+1)a i ,∀iε{0,1, . . . ,r−1}; and
e) outputting an encoded vector that includes the information digits and check part, wherein any two check parts computed according to step (d) are at least l+1 apart.
10. The method according to claim 9 , wherein
r
=
k
×
log
(
2
l
+
1
)
log
⌈
q
2
l
+
1
⌉
.
11. 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 encoding an information vector for use in systematic correction of all symmetric errors of maximum magnitude /comprising:
a) providing a q-ary information vector having k information digits, (x k-1 ,x k-2 , . . . ,x 0 );
b) computing a , the value of (x k-1 ,x k-2 , . . . ,x 0 )mod(2l+1) as a vector over (2l+1) according to the formula
a=y k-1 (2 l +1) k-1 +y k-2 (2 l +1) k-2 +. . .+ y 0 (2 l +1) 0 ,
where y i =x i mod(2l+1),iε{0,1, . . . ,k−1};
c) representing a in radix
⌈
q
2
l
+
1
⌉
number with r digits, (a r-1 ,a r-2 , . . . ,a 0 ),
where
r
≥
k
×
log
(
2
l
+
1
)
log
⌈
q
2
l
+
1
⌉
;
d) computing the check part as c=(c r-1 ,c r-2 , . . . ,c 0 ),
where c i =(2l+1)a i ,∀iε{0,1, . . . ,r−1}; and
e) outputting an encoded vector that includes the information digits and check part, wherein any two check parts computed according to step (d) are at least l+1 apart.
12. The computer program product according to claim 11 , wherein
r
=
k
×
log
(
2
l
+
1
)
log
⌈
q
2
l
+
1
⌉
.
13. 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, wherein any two check symbols are at least l+1 apart.
14. The method according to claim 13 , wherein
r
=
k
×
log
(
2
l
+
1
)
log
⌈
q
2
l
+
1
⌉
.
15. 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 /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
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, wherein any two check symbols are at least l+1 apart.
16. The computer program product according to claim 15 , wherein
r
=
k
×
log
(
2
l
+
1
)
log
⌈
q
2
l
+
1
⌉
.