System and method having optimal, systematic q-ary codes for correcting all asymmetric and symmetric errors of limited magnitude
AssigneeState of Oregon acting by and through the State Board of Higher Education on behalf of Oregon State University
InventorsBella Bose, Noha Elarief
Life of this patent
Estimating the term…
Abstract
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.
Claims16
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, (xk-1,xk-2, . . . ,x0);
- b) computing a, the value of (xk-1,xk-2, . . . ,x0) mod (l+1) as a vector over (l+1) according to the formula
- a=yk-1(l+1)k-1+yk-2(l+1)k-2+. . . +y0(l+1)0, where
- yi=ximod(l+1),iε{0,1, . . . ,k−1};
- c) representing a in radix
- ⌈
- q
- l
- +
- 1
- ⌉
- number with r digits:
- (ar-1,ar-2, . . . ,a0),
- where
- r
- ≥
- k
- ×
- log
-
- (
- l
- +
- 1
- )
- log
-
- ⌈
- q
- l
- +
- 1
- ⌉
- ;
- d) computing the check part, c, according to the formula c=(cr-1,cr-2, . . . ,c0), where ci=(l+1)ai,∀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.
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=πr2
- a) providing a q-ary information vector having k information digits, (xk-1,xk-2, . . . ,x0);
- b) computing a , the value of (xk-1,xk-2, . . . ,x0) mod (l+1) as a vector over (l+1) according to the formula
- a=yk-1(l+1)k-1+yk-2(l+1)k-2+. . . +y0(l+1)0, where
- yi=ximod(l+1),iε{0,1, . . . ,k−1};
- c) representing a in radix
- ⌈
- q
- l
- +
- 1
- ⌉
- number with r digits:
- (ar-1,ar-2, . . . ,a0), where
- r
- ≥
- k
- ×
- log
-
- (
- l
- +
- 1
- )
- log
-
- ⌈
- q
- l
- +
- 1
- ⌉
- ;
- d) computing the check part, c, according to the formula c=(cr-1,cr-2, . . . ,c0), where ci=(l+1)ai,∀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.
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 (cr-1,cr-2, . . . ,c0) 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=(yk-1,yk-2 , . . . ,y0);
- e) computing ei=(yi−x′i) mod (l+1) ;
- and
- computing the corrected codeword, (xk-1,xk-2, . . . ,x0), as xi=x′i+ei, where i=0,1, . . . ,k−1, wherein any two of the check symbols are at least l+1 apart.
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 (cr-1,cr-2, . . . ,c0) 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=(yk-1,yk-2, . . . , y0);
- e) computing ei=(yi−x′i) mod (l+1) ;
- and
- f) computing the corrected codeword, (xk-1,xk-2, . . . ,x0), as x′i+ei, where i=0,1, . . . ,k−1, wherein any two of the check symbols are at least l+1 apart.
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, (xk-1,xk-2, . . . ,x0);
- b) computing a , the value of (xk-1,xk-2, . . . ,x0)mod(2l+1) as a vector over (2l+1) according to the formula
- a=yk-1(2l+1)k-1+yk-2(2l+1)k-2+. . .+y0(2l+1)0,
- where yi=ximod(2l+1),iε{0,1, . . . ,k−1};
- c) representing a in radix
- ⌈
- q
- 2
-
- l
- +
- 1
- ⌉
- number with r digits, (ar-1,ar-2, . . . ,a0),
- where
- r
- ≥
- k
- ×
- log
-
- (
- 2
-
- l
- +
- 1
- )
- log
-
- ⌈
- q
- 2
-
- l
- +
- 1
- ⌉
- ;
- d) computing the check part as c =(cr-1,cr-2, . . . ,c0),
- where ci=(2l+1)ai,∀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.
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, (xk-1,xk-2, . . . ,x0);
- b) computing a , the value of (xk-1,xk-2, . . . ,x0)mod(2l+1) as a vector over (2l+1) according to the formula
- a=yk-1(2l+1)k-1+yk-2(2l+1)k-2+. . .+y0(2l+1)0,
- where yi=ximod(2l+1),iε{0,1, . . . ,k−1};
- c) representing a in radix
- ⌈
- q
- 2
-
- l
- +
- 1
- ⌉
- number with r digits, (ar-1,ar-2, . . . ,a0),
- where
- r
- ≥
- k
- ×
- log
-
- (
- 2
-
- l
- +
- 1
- )
- log
-
- ⌈
- q
- 2
-
-
- l
- +
- 1
- ⌉
- ;
- d) computing the check part as c=(cr-1,cr-2, . . . ,c0),
- where ci=(2l+1)ai,∀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.
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 (cr-1,cr-2, . . . ,c0)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=(yk-1,yk-2, . . . ,y0);
- e) computing ei=(yi−x′i)mod(2l+1) such that −l≦ei≦l;
- and
- f) computing the corrected codeword, (xk-1,xk-2, . . . ,x0), as xi=x′i+ei,
- where i=0,1, . . . ,k−1, wherein any two check symbols are at least l+1 apart.
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 (cr-1,cr-2, . . . ,c0) 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=(yk-1,yk-2, . . . ,y0);
- e) computing ei=(yi−x′i)mod(2l+1) such that −l≦ei≦l;
- and
- f) computing the corrected codeword, (xk-1,xk-2, . . . ,x0), as xi=x′i+ei, where i=0,1, . . . ,k−1, wherein any two check symbols are at least l+1 apart.
Dependencies are inferred from the claim text.