Patent GB-1092916-A (GB)
Title: Decoding apparatus
IPC: H03M13/15
Filed: 1965-03-26
Abstract: 1,092,916. Error arrangements. INTERNATIONAL BUSINESS MACHINES CORPORATION. March 26, 1965 [April 10, 1964], No. 13068/65. Heading G4A. Decoding apparatus capable of identifying error in a received data group constructed in a cyclic code based on an error location polynomial in a Gallois field comprises means for generating coefficients of the error location polynomial from the received data group and multiplying them by particular elements from the field, the sum of the products being obtained and examined for error indicating values thereof. First embodiment (Figs. 1C, 2, not shown). A 15-bit data group in a Bose-Chaudhuri- Hocquenghem code permitting correction of two independent bit errors, and received (12, Fig. 2A, not shown) from storage or transmission means is passed to one of two input buffers (28a, 28b) selected by a flip-flop (42), under control of timing pulses derived from the input bits by a first pulse generator (16). Concurrently, such a data group previously read into the other buffer is read serially by bit at a higher speed under control of a second pulse generator (68, Fig. 2B, not shown) to an input adder (86) of a shift register structure (89, Figs. 2B, 2C, not shown). The latter comprises four first flip-flops (94a to 94d) which can feed respective second flip-flops (104a to 104d). The second flip-flops can feed the first flip-flops with shift and in part via the input adder (86) and a half-adder (120). Under control of the second generator (68) and with a control flip-flop (70, Fig. 2B, not shown) set to " one," the first-to-second and second-to-first feedings occur alternately, both occurring once during each bit time of the input from the input buffer (28a or 28b, Fig. 2A, not shown) to construct in the first flip-flops (94a to 94d) the first power sum S 1  which is the sum of the first powers of the roots of the error location polynomial (these roots specifying the positions in error) and is a parity function. The power sum S 1  is stored in a first multiplier (149, Fig. 2E, not shown)-see below-and also in other flipflops (140a to 140d, Fig. 2D, not shown). The shift register structure (89, Figs. 2B, 2C, not shown) after resetting of its flop-flops now operates as before again, receiving the same input from the input buffer (28a or 28b), except that the first-to-second and second-to-first feedings are at three times the input bit rate, under control of the second generator (68), the control flip-flop (70) being set to " zero." This provides the power sum S 3 , being the sum of the cubes of the roots of the error location polynomial, in the first flip-flops (94a to 94d) from where it is passed to further flip-flops (204a to 204d, Fig. 2K, not shown). Next, after resetting of the flip-flops in the shift register structure (89, Figs. 2B, 2C, not shown), the value of S 1  is returned serially from its flip-flops (140a to 140d, Fig. 2D, not shown), to the input adder (86, Fig. 2B, not shown) of the shift register structure (89), first-to-second and second to-first feedings of the latter now occurring at twice the rate of the input bits, under control of a third pulse generator (199, Fig. 2D, not shown). This produces S<SP>2</SP> 1  in the first flip-flops (94a to 94d) from where it is passed to further flip-flops (238a to 238d, Figs. 2J, 2K, not shown). Logic circuitry comprising AND, OR and modulo-2 adder blocks (Figs. 2G-2K, not shown) produces the quotient S 3 /S 1 , respective bits of which are modulo-2 added to corresponding bits of S<SP>2</SP> 1  (2j-30 to 2j-33, Figs. 2J, 2K, not shown) to produce the elementary symmetric function # 2 , one of the coefficients of the error location polynomial. This function is stored in a second multiplier (256, Fig. 2F, not shown). The first multiplier (149, Fig. 2E, not shown) already has the elementary symmetric function # 1  since this is equal to S 1 . The multipliers (149, 256) multiply their inputs by respective powers of a primitive element of the field (these powers being themselves elements of the field) to produce α# 1  and α<SP>2</SP># 2  respectively. The first multiplier (149, Fig. 9, not shown) has first flip-flops (9-1 to 9-4) to store its input. Alternately, these feed respective second flip-flops (9-7 to 9-10), and the latter feed the first flip-flops (9-1 to 9-4) with shift and in part through a half-adder (9-19). The second multiplier (256, Fig. 10, not shown) is similar but has two half-adders (10-22, 10-21). During this operation, corresponding bits in the first flip-flops of the two multipliers and of a (constant) elementary symmetric function # 0  are modulo-2 added in half-adders (280 to 283, 288 to 291, Figs. 2E, 2F, not shown), and whenever the result is zero, as detected by a NOR gate (296), the corresponding bit of the input data group is inverted in a half-adder (298). Modifications.-Fig. 1D (not shown), shows another embodiment in which the power sums S 1 , S 3  are obtained from the input bits, which also proceed via a buffer (1d-5) to a modulo-2 adder (1d-64) for correction. The power sums S 1 , S 3  are multiplied by a and α<SP>3</SP> respectively and applied to logic circuitry involving ANDs, inverters, and modulo-2 adders, some of the latter feeding an OR circuit (1d-60) the inverted (1d-61) output of which feeds the modulo-2 ,adder (1d-64) used for correction. Fig. 1E (not shown), shows an embodiment capable of correcting three independent bit errors which performs correction in accordance with the values of the first power sum S 1  and two determinants reducing to expressions in the power sums S 1 , S 3 , S 5 , the latter being multiplied by a, α<SP>3</SP>, α<SP>5</SP> respectively before use. In the above embodiments, the data group is processed high order first, but this may be done low order first, the multiplying by field elements being replaced by dividing by them, which is equivalent to multiplying by other field elements. Operation may be parallel rather than serial.