High speed encoder for non-systematic codes
First Claim
1. A serial shift encoder for generating parity characters having intermediate symbol locations between first and second message blocks in a codeword of a code generator polynomial g(x), comprising:
- first means for generating first products of a successive character of the first measage block multiplied by corresponding coefficients of g(x);
second means for generating second products of a successive character of the second message block multiplied by corresponding coefficients of a remainder h(x) of the division by g(x) an algebraic shift factor xn ; and
third means comprising a series of adders, a first of said series of adders for generating a sum of (a) a preselected one of said first products and (b) a preselected one of said second products, a remainder of said series of adders for generating in a corresponding one of said adders the sum of (a) the contents of a previous one of said adders, (b) a respective one of said first products and (c) a respective one of said second products, said third means serially shifting the sum generated in each adder to a succeeding adder in said series.
1 Assignment
0 Petitions
Accused Products
Abstract
Interleaved cyclic error correction encoded binary data, of the type employed in the compact audio disk standard for example, in which the parity characters are located in the middle of a codeword, are encoded by a serial encoder to greatly increase the speed at which such data may be recorded. In the invention, the message characters are treated as two polynomials, a left-hand sub-codeword or message block representing the message characters to the left of the parity characters and a right-hand sub-codeword or message block representing the message characters to the right of the parity characters. The encoder of the invention has two parallel inputs which simultaneously receive the message characters of the right-hand and left-hand sub-codewords, respectively, each input receiving one character at a time in serial fashion. The encloder is a serial register in which each stage receives the sum of the contents of the previous stage and (a) the product of the current character of the left-hand sub-codeword multiplied by a respective coefficient of the code generator polynomial and (b) the product of the current character of the left-hand sub-codeword multiplied by a respective coefficient of the residue of an algebraic shift factor, whose degree is equal to the length of the cyclic error correction code minus the length of the sub-codeword, divided by the code generator polynomial.
43 Citations
16 Claims
-
1. A serial shift encoder for generating parity characters having intermediate symbol locations between first and second message blocks in a codeword of a code generator polynomial g(x), comprising:
- first means for generating first products of a successive character of the first measage block multiplied by corresponding coefficients of g(x);
second means for generating second products of a successive character of the second message block multiplied by corresponding coefficients of a remainder h(x) of the division by g(x) an algebraic shift factor xn ; and third means comprising a series of adders, a first of said series of adders for generating a sum of (a) a preselected one of said first products and (b) a preselected one of said second products, a remainder of said series of adders for generating in a corresponding one of said adders the sum of (a) the contents of a previous one of said adders, (b) a respective one of said first products and (c) a respective one of said second products, said third means serially shifting the sum generated in each adder to a succeeding adder in said series. - View Dependent Claims (2, 3, 4, 5, 6, 7)
- first means for generating first products of a successive character of the first measage block multiplied by corresponding coefficients of g(x);
-
8. A serial interleaving and encoding system, comprising:
-
(I) an outer serial shift encoder for generating parity characters having intermediate symbol locations between first and second message blocks in a codeword of a code generator polynomial g(x), comprising; (A) first means for generating first products of a successive character of the first message block multiplied by corresponding coefficients of g(x), (B) second means for generating second products of a successive character of the second message block multiplied by corresponding coefficients of a remainder h(x) of the division by g(x) of an algebraic shift factor xn, (C) third means comprising a series of adders for generating in a corresponding one of said adders the sum of (a) the contents of a previous one of said adders, (b) a respective one of said first products and (c) a respective one of said second products, and serially shifting the sum generated in each adder to a succeeding adder in said series; (D) fourth means for serially sending all of the characters of said first and second message blocks to said first and second means, respectively, and to an encoder output node and then shifting the current sums in said adders to said encoder output node; (II) a first serial interleaver having an input and an output, said first serial interleaver comprising; (A) random access memory for writing characters received at said input into memory locations and for reading characters from said memory locations to said output; (B) up-counter unit for specifying an ordered sequence of said memory locations during one of reading and writing of said characters in said random access memory; (C) read-only memory for specifying a scrambled sequence of said memory locations during the other of said reading and writing of said characters in said random access memory; and (III) an inner serial encoder for encoding a block of characters received from said output of said first serial interleaver, wherein said first serial interleaver input is connected to an output node of said inner encoder. - View Dependent Claims (9)
-
-
10. A method for generating parity characters having intermediate symbol locations between first and second message blocks in a codeword of a code generator polynomial g(x), comprising:
-
first generating first products of a successive character of the first message block multiplied by corresponding coefficients of g(x); second generating second products of a successive character of the second message block multiplied by corresponding coefficients of a remainder h(x) of the division by g(x) of an algebraic shift factor xn ; third generating in a corresponding one of a series of adders the sum of (a) a respective one of said first products and (b) a respective one of said second products, wherein the sum of each of said adders following a first of said series of adders includes the contents of a previous one of said series of adders; and serially shifting the sum generated in each adders to a succeeding adder in said series. - View Dependent Claims (11, 12, 13, 14, 15, 16)
-
Specification