Method of encoding signals with binary codes
AssigneeThe United States of America as represented by the Director, National Security Agency
InventorDonald W. Newhart
Life of this patent
Estimating the term…
Abstract
A method of encoding a communication signal by selecting a cyclic code, establishing a generator polynomial, generating a polynomial using the generator polynomial, forming a matrix from the generated polynomial, receiving data to be encoded, appending zeros to the received data, calculating a syndrome of the matrix, calculating check values from the syndrome, appending the check values to the received data, and encoding the received data with appended check values using the generator polynomial.
Claims2
A method of encoding a signal on a computer, comprising the steps of:
- a) selecting a user-definable binary cyclic code, the user-definable binary cyclic code having a user-definable length n and a user-definable dimension k;
- b) establishing a generator polynomial g(x) having coefficients (g0, g1, g2 . . . , gn-k);
- c) setting
- h
-
- (
- x
- )
- =
- (
- x
- n
- -
- 1
- )
- g
-
- (
- x
- )
- with coefficients (h0, h1, h2, . . . , hk) and
- forming
-
-
- H
- =
- [
- h
- k
- h
- k
- -
- 1
- h
- k
- -
- 2
- …
- h
- 0
- 0
- 0
- …
- 0
- 0
- h
- k
- h
- k
- -
- 1
- …
- h
- 1
- h
- 0
- 0
- …
- 0
- …
- …
- …
- …
- …
- …
- 0
- 0
- 0
- …
- h
- k
- h
- k
- -
- 1
- h
- k
- -
- 2
- …
- h
- 0
- 0
- 0
- 0
- …
- 0
- h
- k
- h
- k
- -
- 1
- …
- h
- 1
- h
- 0
- ]
- ;
- d) receiving data to be encoded, the data having the coefficients (a1, a2, . . . , ak);
- e) appending (n−k) zeros to the received data forming an n-long vector, {right arrow over (r)}=(0, 0, . . . , a1, a2, . . . , hk);
- f) calculating the binary syndrome {right arrow over (s)}=H{right arrow over (r)}t on the computer by performing an exclusive-OR function of (n−k) segments of (r0, r1, r2, . . . , rn-i) according to the coefficients (h0, h1, h2, . . . , hk);
- g) calculating the (n−k) check values L{right arrow over (s)}t, where
- L
- =
- [
- g
- n
- -
- k
- g
- n
- -
- k
- -
- 1
- g
- n
- -
- k
- -
- 2
- …
- g
- 1
- 0
- g
- n
- -
- k
- g
- n
- -
- k
- -
- 1
- …
- g
- 2
- 0
- 0
- …
- …
- 0
- 0
- …
- g
- n
- -
- k
- g
- n
- -
- k
- -
- 1
- 0
- 0
- …
- 0
- g
- n
- -
- k
- ]
- ;
- h) appending the received data with the (n−k) check values calculated in step (g);
- and
- i) encoding the received data on the computer using the generator polynomial established in step (b).
A method of encoding a signal using a shortened code on a computer, comprising the steps of:
- a) selecting a user-definable shortened binary cyclic code, the user-definable binary cyclic code having a user-definable length n, a user-definable dimension k, and is shortened by a total of m<k bits, where m are high-order data bits, wherein the m high-order data bits are processed as zeros;
- b) establishing a generator polynomial g(x) having coefficients (g0, g1, g2, . . . , gn-k);
- c) setting
- h
-
- (
- x
- )
- =
- (
- x
- n
- -
- 1
- )
- g
-
- (
- x
- )
- with coefficients (h0, h1, h2, . . . , hk) and
- forming
-
-
- H
- =
- [
- h
- k
- h
- k
- -
- 1
- h
- k
- -
- 2
- …
- h
- 0
- 0
- 0
- …
- 0
- 0
- h
- k
- h
- k
- -
- 1
- …
- h
- 1
- h
- 0
- 0
- …
- 0
- …
- …
- …
- …
- …
- …
- 0
- 0
- 0
- …
- h
- k
- h
- k
- -
- 1
- h
- k
- -
- 2
- …
- h
- 0
- 0
- 0
- 0
- …
- 0
- h
- k
- h
- k
- -
- 1
- …
- h
- 1
- h
- 0
- ]
- ;
- d) receiving data to be encoded, the data having the coefficients (a1, a2, . . . , ak);
- e) appending (n−k) zeros in front of the received data and the minimum {n−k−1, m}zeros to the end of the received data, forming an n-long vector, {right arrow over (r)}=(0, 0, . . . , a1, a2, ak);
- f) calculating the binary syndrome {right arrow over (s)}=H{right arrow over (r)}t on the computer by performing an exclusive-OR function of (n−k) segments of (r0, r1, r2, . . . , rn-1) according to the coefficients (h0, h1, h2, . . . , hk);
- g) calculating the (n−k) check values L{right arrow over (s)}t, where
- L
- =
- [
- g
- n
- -
- k
- g
- n
- -
- k
- -
- 1
- g
- n
- -
- k
- -
- 2
- …
- g
- 1
- 0
- g
- n
- -
- k
- g
- n
- -
- k
- -
- 1
- …
- g
- 2
- 0
- 0
- …
- …
- 0
- 0
- …
- g
- n
- -
- k
- g
- n
- -
- k
- -
- 1
- 0
- 0
- …
- 0
- g
- n
- -
- k
- ]
- ;
- h) appending the received data with the (n−k) check values calculated in step (g);
- and
- i) encoding the received data on the computer using the generator polynomial established in step (b).
Dependencies are inferred from the claim text.