[go: up one dir, main page]

WO1997013328A1 - Device and method for error correcting coding, and device and method for error correcting decoding - Google Patents

Device and method for error correcting coding, and device and method for error correcting decoding Download PDF

Info

Publication number
WO1997013328A1
WO1997013328A1 PCT/JP1996/002866 JP9602866W WO9713328A1 WO 1997013328 A1 WO1997013328 A1 WO 1997013328A1 JP 9602866 W JP9602866 W JP 9602866W WO 9713328 A1 WO9713328 A1 WO 9713328A1
Authority
WO
WIPO (PCT)
Prior art keywords
data
input
output
bit
bits
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP1996/002866
Other languages
English (en)
French (fr)
Inventor
Hiroyuki Yabuno
Takashi Yumiba
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Panasonic Holdings Corp
Original Assignee
Matsushita Electric Industrial Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Matsushita Electric Industrial Co Ltd filed Critical Matsushita Electric Industrial Co Ltd
Priority to US08/849,388 priority Critical patent/US5914969A/en
Priority to EP96932801A priority patent/EP0806839B1/en
Priority to DE69618930T priority patent/DE69618930T2/de
Priority to JP51415497A priority patent/JP3622981B2/ja
Publication of WO1997013328A1 publication Critical patent/WO1997013328A1/ja
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
    • H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
    • H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
    • H03M13/13—Linear codes
    • H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
    • H03M13/151—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes using error location or error correction polynomials

Definitions

  • the present invention relates to an error correction coding device and method, and an error IT correct decoding device and method.
  • a digital recording device or digital communication device records or reproduces digital data, or transmits or receives digital data, it encodes an error code for correcting an error in the digital data.
  • the present invention relates to an error correction encoding device and method, and an error correction decoding device and method for decoding an error correction code.
  • error correction codes are used in various devices that handle digital data.
  • the Reed-Solomon code is also a kind of such an error correction code, and is mainly used for a digital recording device such as a PD drive unit using a phase change.
  • a Reed-Solomon code consists of a codeword consisting of elements of the Galois field GF (2 N ) whose original number is 2 N.
  • N is a primitive element of GF (2 N )
  • the generator polynomial is This is a multi-element traveling hamming skull expressed by the following equation.
  • G (X) (X in a flat 0) ( ⁇ - 1) - CX- 6 - 2 - (1) where including formula (1), hereinafter, on all operations Galois GF (2 N) Do. D represents the minimum inter-symbol distance.
  • the codeword for Reed-Solomon Hikari is generated as follows. Expressing the information word vector I as
  • I (X) " ⁇ X 1 + i,-X k- 20 ... + i 2 'X + i-(3)
  • i 0 , i ,, ⁇ , i k- Are coasting symbols, respectively, and correspond to the Galois field GF (vector representation of two higher elements, with N bits as a unit, for the bit data that is the source of the information.
  • the code polynomial A (X) can be obtained from the information polynomial I (X) and the generator polynomial G (X) using the following equation.
  • a (X) Q (X) ⁇ G (X)... (7) holds. Since A (X) obtained by Eq. (7) can be divided by the generator polynomial G (X), it becomes a sign polynomial. Let the sign polynomial R (X) be
  • R n - have i ⁇ ⁇ ⁇ ⁇ have 1 + r n - 2 ⁇ ⁇ ⁇ - 2 ten ... + 7 ⁇ ⁇ ⁇ + r 0
  • the code word vector ⁇ expressed by equation (10) includes the information word vector I as it is. It can be seen that this is an organization code.
  • the codeword vector A is an (n, k) systematic code.
  • R (r 0. R !. ⁇ , r disturb -k -!... (11) is the parity word vector.
  • FIG. 12 shows an example of a conventional error correction coding device using a Reed-Solomon code. This circuit performs division of a polynomial having coefficients of Galois field GF (2 N ). In FIG. 12, the error correction coding device
  • An initial value setting circuit 207 for clearing and initializing the contents of the 8-bit latches 183 to 194 to 0 upon reset.
  • the input data is an exclusive OR
  • the data input to the first input terminal of the 206 and output from the output terminal of the exclusive-OR calculator 206 are input to the latch 183 via the coefficient multiplier 171 and the coefficient multiplier g 1 are input to the exclusive OR operators 195 to 205 through 2 to 183, respectively.
  • the latches 183 to 194 and the exclusive OR operators 195 to 206 are arranged alternately and are vertically connected so that data is transmitted from the latch 183 to the latch 194.
  • the primitive polynomial m (X), the primitive element person, and the generator polynomial G (X) are defined as follows.
  • the exclusive OR unit 206 When 0 is input to the exclusive OR unit 206, the first coasting symbol i. 00, 8 exclusive OR of 00H as the output data of the bit Toratchi 194 is calculated, the data of the operation result is input to the Galois field coefficient multipliers 171 to 182.
  • H in 00H indicates hexadecimal notation, and so on.
  • the data input to the Galois field coefficient multipliers 171 to 182 is d.
  • the first information symbol i. Data d 00o which is an exclusive OR of 00 and data 00H can be expressed by the following equation.
  • the output data of the Galois field coefficient multipliers 171 to 182 are stored in 8-bit latches 183 to 194, respectively.
  • the data stored in each of the latches 183 to 194 is p.
  • D0 to Pin these data values correspond to the results of performing the operations in column numbers R13 to R2 in FIG. 13 and for three rows in step S101.
  • the addition symbol in FIG. 13 indicates an exclusive OR operation, and hereinafter, the operation EOR indicates an exclusive OR operation.
  • output data of the Galois field coefficient multipliers 171 to 182 are stored in 8-bit latches 183 to 194, respectively.
  • the data stored in each of the latches 183 to 194 is set to PC12 to PC12. Assuming 23, these data values are
  • a first object of the present invention is to solve the above problems, to achieve a practical coding speed, to realize a small-scale circuit configuration compared to the conventional technology, and to change the device configuration. It is an object of the present invention to provide an error correction coding apparatus and method capable of freely changing the minimum inter-code distance d without any need.
  • a second object of the present invention is to realize a decoding circuit that has a practically useful decoding degree, can be realized with a small-scale circuit configuration as compared with the conventional technology, and has a minimum inter-code distance without changing the device configuration.
  • An object of the present invention is to provide an error correction decoding device and a method capable of freely changing d.
  • a plurality of seed data on the Galois field of each input data and each coefficient of the Reed-Solomon code generator polynomial are calculated in advance, and the plurality of product data are converted into a plurality of b Means for storing data in advance as a set of data;
  • a storage means for mi consisting of m natural number storage devices each having a storage capacity of N x b bits;
  • the product data storage means is arranged so that a plurality of product data stored in the product data storage means are fired in parallel as a set of b product data.
  • Each has N xb bit first and second input terminals, A plurality of b pieces of product data read in parallel from the product data storage means by the control means are input to a first input terminal, and data input to the first input terminal; and An exclusive-OR calculating means for performing an exclusive-OR operation with the data input to the CPU and outputting the operation result data;
  • the data stored in the m useful devices are selectively read and output sequentially for each storage device, and the upper N x ( b-1) bits of data are output to the lower Nx (b-1) bits of the second input terminal of the exclusive-OR operation means and output from the exclusive-OR operation means
  • First selection means for controlling the first storage means so as to selectively and sequentially switch the data of the operation result to one of the m storage devices
  • Second storage means for temporarily using data and outputting to the upper N bits of the second input terminal of the exclusive OR operation means;
  • parity data is generated in the m useful devices of the first convenient unit, and the m input devices are sequentially followed by the m input devices.
  • the read control unit, the first selection unit, and the second selection unit include a predetermined program stored in another storage device.
  • St 3 is composed by the central processing unit that executes Further, according to the error correction decoding apparatus according to the present invention, using a lead 'Solomon code having an original on that having a number original of 2 N Galois GF (2 N), natural numbers per symbol N In an error correction decoding device that decodes an error correction code encoded for input data of bits,
  • a received word storage unit including a plurality of received symbols including the input data and parity data for the input data, and storing an input received word for each received symbol;
  • a residue calculating means comprising the error correction coding device, calculating and outputting a residue for the input word received using the generator polynomial of the Reed-Solomon code
  • An error value and error position calculating means for calculating and outputting a set of an error position in the received word and an error value corresponding to the error position S based on the residue output from the residue calculating means;
  • the received symbol at the error position stored in the received word writing means is read out from the received word storage means and output.
  • the scent for correcting the received symbol at the error position is obtained.
  • an embedding control means By inputting the result of the operation result output from the exclusive OR operation means to the error position in the received word storage means, the scent for correcting the received symbol at the error position is obtained. And an embedding control means. Further, according to the error correction coding method of the present invention, the number of elements of 2N is used. Leading with the Galois field GF (2 N) on the original. Using Solomon code, the error correction coding method for sign-the error correction code to the input data of natural number N bits Bok per symbol,
  • a plurality of product data on the Galois field between each input data and each coefficient of the above-mentioned Reed-Solomon code generator polynomial are calculated in advance, and the above-mentioned plurality of product data is multiplied by b products for each address. Pre-storing the data as a set in the product data storage means;
  • the product data storage means is controlled so that a plurality of product data stored in the product data storage means are read in parallel as a set of a plurality of b product data. Steps and
  • exclusive OR operation means having first and second input terminals of N ⁇ b bits each, a plurality of b pieces of edge data read in parallel from the product data storage means are supplied to the first input terminal. Calculating an exclusive OR of the input data and the data input to the first input terminal and the data input to the second input terminal, and outputting the operation result data;
  • the data useful for the first storage means of the m storage devices each having a storage capacity of NX b bits are selectively read and output sequentially for each storage device.
  • the upper N x (b—1) bit data of the N x b bit data that is output after being ejected is converted to the lower N x (b—) of the second input terminal of the exclusive OR operation means.
  • the data of the operation result output from the exclusive-OR operation means is selectively switched and written to one of the m memory devices in order. Controlling a first convenient means;
  • the second storage means having an N-bit storage capacity
  • the lower part of the N ⁇ b-bit data selectively output from one of the m useful devices is used.
  • parity data is generated in the m storage devices of the first useful means, and the m storages are used for the input data.
  • Selectively outputting the parity data generated in the m storage devices sequentially by selectively switching the storage device for each storage device.
  • the lead To have use Solomon code, a natural number N bits per symbol with a Galois field GF (2 N) on the original with the original number of 2 N
  • FIG. 1 is a block diagram of the error correction encoding device according to the first embodiment of the present invention.
  • FIG. 2 is a timing chart showing the operation of the error correction coding apparatus of FIG.
  • FIG. 3 is a block diagram of the error correction encoding device according to the second embodiment of the present invention.
  • FIG. 5 is a flowchart showing an encoding process executed by the CPU 61 of the error correction encoding device of FIG.
  • FIG. 6 is a flowchart showing the initialization processing (step S1) which is a subroutine of FIG.
  • FIG. 7 is a flowchart showing a codeword generation process (step S2) which is a subroutine of FIG.
  • FIG. 8 is a flowchart showing the subroutine process P1 (step S7) of FIG.
  • FIG. 10 is a flowchart showing the subroutine process P3 (step S37) in FIG.
  • FIG. 11 is a flowchart showing the subroutine process P4 (step S24) of FIG. It is a one-chart.
  • FIG. 12 is a block diagram of a conventional error correction coding device.
  • FIG. 15 is a block diagram of the error correction decoding device according to the third embodiment of the present invention.
  • FIG. 1 is a block diagram showing a configuration of an error correction encoding device according to a first embodiment of the present invention. The error of the first embodiment.
  • Delay circuit 300 including three symbol delay circuits 301 to 303
  • An 8-bit output data selector 310 is provided.
  • 8-bit input data is input to the first input terminal of the exclusive-OR operator 11 and output via the d contact of the output data selector 310. Output as data.
  • the output data from the output terminal of the exclusive OR calculator 18 is input to the second input terminal of the exclusive OR calculator 11.
  • the clock CLK is input to the quaternary counter 13 and the latches 29 and 27.
  • the quaternary counter 13 counts the input clock CLK, resets it to 0 when the count value reaches 4, and outputs the 2-bit data of the count value via the latch 29 to the upper 2 bits of the address.
  • the 2-bit latch 29 latches the 2-bit data of the count value of the quaternary counter 13 at the falling edge of the clock CLK.
  • the decoder 28 delays the clock CLK half-cycle by half the clock CLK half-period. Is output to the latch 27. Also, when the output data of the quaternary counter 13 indicates a value of “1”, the decoder 24 delays the clock signal CLK by a half cycle time and outputs a pulse signal having a half cycle width of the clock CLK to the latch 20. Output. Further, when the output data of the quaternary counter 13 indicates a value of “2”, the decoder 25 latches a pulse signal having a width of a half cycle of the clock CLK with a delay of a half cycle of the clock CJLK. 2 Output to 1.
  • the decoder 26 latches a pulse signal having a width of a half cycle of the clock CLK with a delay of a half cycle of the clock CLK. Output to 22.
  • the 8-bit latch 12 latches the 8-bit data from the exclusive OR operation unit 11 at the rising edge of the clock CLK of the pulse signal from the decoder 26 and stores the lower 8 bits in the ROM 14. Output as address.
  • a result obtained by multiplying the input symbol in the vector expression by a predetermined coefficient on the Galois field is stored in the vector expression in advance.
  • Input data is given as the lower 8 bits of the address, and the upper 2 bits of the address are used to switch coefficients.
  • the 32-bit output data from the data terminal of the ROM 14 is input to the first input terminals of the four exclusive OR operators 15 to 18, and the 32-bit data output from the output terminals is Input to the input terminal of 32-bit bus selector 19.
  • the 8-bit output data output from the exclusive OR calculator 18 is input to the second input terminal of the exclusive OR calculator 11.
  • the 32-bit bus selectors 19 and 23 are bus selectors for switching four circuits in conjunction with four 8-bit buses.
  • the 32-bit bus selector 19.23 switches to the bottommost d contact when the selection signal is "0" Be bus!
  • the input terminal of the selector 19 and the output terminal of the bus selector 23 are open.
  • the selection signal is "1”
  • the 32-bit bus selectors 19 and 23 are switched to the uppermost contact a, and the input terminal of the bus selector 19 is connected to the 32-bit latch 20.
  • the bus selector 23 is connected to the output bus of the 32-bit latch 20 while being connected to the input bus.
  • the 32-bit bus selector 19.23 is switched to the normally closed contact at the second position from the top, and the input terminal of the bus selector 19 is switched to the 32-bit latch.
  • the bus selector 23 is connected to the output bus of the 32-bit latch 21 while being connected to the input bus 21.
  • the 32-bit bus selectors 19 and 23 are switched to the c-contact at the third position from the top, and the input terminals of the bus selector 19 are 3 2
  • the bit selector 22 is connected to the input bus of the bit latch 22 and the bus selector 23 is connected to the output bus of the 32 bit latch 22.
  • the upper 24 bits of the 32-bit output data output from the bus selector 23 are input to the second input terminals of the exclusive OR operators 17.18, 19
  • the lower 8 bits of the 32-bit output data output from the bus selector 23 are input via the 8-bit latch 27 to the ⁇ 2 input of the exclusive-OR operation unit 15. Input to the terminal.
  • the 8-bit latch 27 latches the input 8-bit data at the rising edge of the clock CLK, and then outputs the data to the second input terminal of the exclusive-OR operator 15.
  • the latched data is cleared to 0.
  • the 32-bit output data output from the 32-bit latch 20 is input to the symbol delay circuit 301, and the symbol delay circuit 301 outputs the input data of the 32-bit data.
  • the upper 8-bit data is output via the b-contact of the 8-bit bus selector 310 without delay after the coasting symbol output from the a-contact of the bus selector 310 without delay.
  • the output timing of this output data is referred to as reference output timing.
  • the 32-bit output data output from the 32-bit latch 21 is input to the symbol delay circuit 302, and the symbol delay circuit 302 outputs the data of the input 32-bit data.
  • the 32-bit output data output from the 32-bit latch 22 is input to the symbol delay circuit 303, and the symbol delay circuit 303 outputs the data of the 32-bit data.
  • a parity word of 32 bits 4 symbols stored in the latch 20 by error correction coding and error correction
  • the output data consists of a 32-bit parity word of 4 symbols encoded and stored in latch 21 and a 32-bit parity word of 4 symbols stored in latch 22 and error correction encoded.
  • a bus ! Output from selector 310.
  • FIG. 2 is a timing chart showing the operation of the error correction coding apparatus of FIG. is there.
  • the input data is 8 bits and is input once for every 4 pulses of the clock CLK.
  • the initial value of the quaternary counter 13 is set to 2
  • the initial values of the 8-bit latches 12, 27, and the 32-bit latches 20, 21, and 22 are set to 0, and the initial value of the 2-bit latch 29 is set to 0. Is done.
  • Tables 1 and 2 show the contents of data stored in the ROM 14.
  • Table 1 ⁇ Beauty Table 2, or k] 2 are the coefficients of the generator polynomial G (X) shown in equation (14), there Naha formula primitive element of the Galois field GF (2 8) shown in (13) ,
  • the product symbol represents the product on the Galois field.
  • N (where m is a natural number from 1 to 12 and n is an integer greater than or equal to 0) are both elements of the Galois field GF (2 8 ). Therefore, the product of and is also an element of the Galois field GF (2 8 ). Since the vector representation corresponds to an 8-bit numerical value, the numerical data of the product is stored in the ROM 14 in advance.
  • address # is the upper two bits of the ROM 14 address
  • address L is the lower eight bits of the ROM 14.
  • b [31,..., 24] is the coefficient data of the most significant 8 bits
  • b [2 3...., 16] is the coefficient data of the next upper 8 bits
  • b [ 15, ..., 8] is the coefficient data of the next upper 8 bits
  • b [7, ⁇ , 0] is the coefficient data of the lower 8 bits.
  • Table 3 is a conversion table for converting the representation should the base-vector representation of the original on the Galois field GF (2 8). Table 3 is provided for reference, and is not data used directly in this embodiment. As is clear from Table 3, if the data value of the address L of the ROM 14 shown in Tables 1 and 2 is converted into an exponential expression, ⁇ ⁇ (where ⁇ is 0 It is understood that it corresponds to the part of the above. Therefore, in ROM 14, for example, 0 is input to address ⁇ , and vector expression is made to address L (8 bits). Of by entering the elements of the Galois field GF (2 8), ROM14 is engaged number k of the generator polynomial. K. K, 0, k e and it can be seen that the output product of the Galois field values entered in the address L .
  • the 32-bit bus selector 19.23 selects the 32-bit latch 22.
  • the input data of the 8-bit exclusive OR gate 18 is composed of data 00 ⁇ which is the lower 8 bits of the output data of the ROM 14 and the 16th bit of the output data of the 32-bit latch 22. Since the data is 00H corresponding to the ninth bit from the data, the output data of the 8-bit exclusive OR operator 18 is 00H.
  • the input data of the 8-bit exclusive-OR unit 11 becomes the data 00H which is the output data of the 8-bit exclusive-OR unit 18 and the input data io, and the 8-bit latch 12 Is the data i. 00 is stored. Therefore, the data d D0 [l in FIG. 2 can be expressed by equation (15).
  • the 8-bit exclusive OR calculator 15 outputs the output data of the 8-bit latch 27 and the exclusive OR data of the upper 8 bits of the output data of the ROM 14, and the 32-bit latch 27 outputs the data.
  • G-bit exclusive OR calculators 16, 17, and 18 output 24-bit data of the exclusive OR of the upper 24 bits of output data of 22 and the lower 24 bits of output data of ROM 14. are doing.
  • the output data of the four 8-bit exclusive OR operators 15, 16, 17, and 18 is damaged by the 32-bit latch 22.
  • the lower 8 bits of the data previously written to the 32-bit latch 22 are written to the 8-bit latch 27.
  • the data written to the 32-bit latch 22 is 00000000H.
  • the data permeated into the 8-bit latch 27 is 00H.
  • the lower 8 bits of the address given to ROM14 are d. 00, and the upper two bits become "3".
  • the data as shown in Table 1 is stored in the ROM 14, and the calculation of the product on the Galois field can be obtained by referring to the table.
  • the ROM 14 since the upper two bits of the address are "3", the ROM 14 outputs data 00000000H from its data terminal. Therefore, when the output data AD of the ROM 14 in FIG. 2 is expressed by being divided into 8 bits, the following expression can be obtained.
  • Ao (0 OH. 0 OH. 0 OH.
  • a a (k 12d 000, k lo ⁇ d ooo.k 9-Q oo D)
  • the 32-bit bus selector 19.23 selects the 32-bit latch 20.
  • the 8-bit exclusive-OR calculator 15 outputs the exclusive-OR data of the 8-bit output data of the 8-bit latch 27 and the upper 8 bits of the output data of the ROM 14, and 32-bit latch
  • the upper 24 bits of the output data of the 20 and the lower 24 bits of the output data of the ROM 14 are exclusive-ORed, and the 8-bit exclusive-OR units 16.17, 18 output the data. are doing. Therefore, the 32-bit output data of the above-described 8-bit exclusive-OR units 15.16, 17, and 18 are damaged by the 32-bit latch 20.
  • the lower 8 bits of the data previously written to the 32-bit latch 20 are written to the 8-bit latch 27.
  • the output data of the 8-bit latch 27 is data 00H
  • the upper 24 bits of the output data of the 32-bit latch 20 are also data 000000H.
  • the data itself is expressed by 18). Therefore, it is the output data of the 32-bit latch 20 in FIG. 2 (Pooo. ⁇ . ⁇ 002, P 003) can be expressed by the following equation.
  • the data input to the 8-bit latch 27 is data 00H.
  • the lower 8 bits of the address given to ROM14 become data dooD, and the upper 2 bits become "1". Therefore, the output data A 2 of ROM 14 in FIG. 2 can be expressed by the following equation.
  • a 2 (k e * ⁇ ooo k 7 ⁇ Q ooo> k 6 ⁇ d 0 oo k 5 -.. ⁇ . ⁇ .)
  • the output data A 3 of ROM 14 can be expressed by the following equation. .
  • a 3 (k 4 ⁇ d 000, k 3 ⁇ d 000. k 2 ⁇ d ooo. Ki ⁇ d ooo)
  • the 8-bit latch is synchronized with the falling edge of the fifth clock CLK. 1 2
  • the output data changes. Specifically, at the rising edge of the output pulse signal of the decoder 26, the 32-bit bus selectors 19, 23 select the 32-bit latch 22, which is the same as for the first clock CLK.
  • To The input data of the 8-bit exclusive-OR operator 11 becomes the output data Pou of the 8-bit exclusive-OR operator 18 and the input data i001 , and the 8-bit latch 12 has Data d expressed by equation (15). . , Are stored.
  • the sum sign means the operation of the sum on the Galois field.
  • the 32-bit bus selectors 19 and 23 have selected the 32-bit latch 20.
  • the output data of the 8-bit latch 27 is 00H
  • the upper two bits of the output data of the 32-bit latch 20 are:
  • the data p which is the lower 8 bits of the data value before the damage of the 32-bit latch 20. 03 is simultaneously input to the 8-bit latch 27.
  • the lower 8 bits of Adoresu given to the ROM14 data d 00 j next, the upper two bits are set to "1".
  • the output data B 3 of the ROM 4 can be expressed by the following equation.
  • the output data of the 8-bit exclusive OR operator 18 is p 023, so that the data d. 02 can be expressed by the following equation. .
  • each of the coefficients of the generator polynomial and a plurality of product data on the Galois field of the input information symbol are calculated, and four for each address
  • the product data storage means is configured to store the product data of the product data as a set, and to read the product data of four sets in parallel (simultaneously) from the exclusive-OR operation units 15 to 32, which is a 32-bit product data storage means.
  • the ROM 1 storing a plurality of product data 4 to 4 sets of product data are configured as a set so that they can be read out in parallel (simultaneously) to the exclusive-OR units 15 to 18, processed simultaneously using 4 sets of product data, and 3 sets Since the encoding operation is performed by selectively and repeatedly using the 32-bit latches 20 to 22 of FIG. 1, the circuit configuration is changed to the circuit configuration of the prior art error correction encoding apparatus of FIG.
  • the error correction code can be extremely simplified as compared with the configuration, and can be operated efficiently and at high speed, and the error correction code can be encoded at an encoding speed that can be put to practical use.
  • the circuit configuration is changed by increasing the number of 32-bit latches 20.21, 22 constituting the first memory means to a few m which is 3 or more and changing the contents of the ROM 14 accordingly. Without error correction, even a similar circuit can encode an error-correcting code with a longer minimum inter-code distance d.
  • FIG. 3 is a block diagram showing a configuration of the error correction coding device according to the second embodiment of the present invention.
  • the error correction coding apparatus according to the second embodiment is a block diagram showing a configuration of the error correction coding device according to the second embodiment of the present invention.
  • the error correction coding apparatus according to the second embodiment is a block diagram showing a configuration of the error correction coding device according to the second embodiment of the present invention.
  • a harmful ROM read-only memory composed of, for example, an EP ROM or an EEPROM, which is an encoding processing program executed by the CPU 61 and data necessary for executing the program.
  • a queue memory 72 which is a first convenient means for forming a shift register, which is a FIFO (First-in First-out) memory, having a plurality of m 32-bit latches 72-1 to 72-m.
  • a 32-bit latch 69 for temporarily latching and reading the contents of the queue memory 72 under the control of the CPU 61;
  • a part of the 32-bit latch 69 comprising an 8-bit latch 68 as second storage means for latching the lower 8 bits of data in the 32-bit latch 69.
  • a 32-bit m-stage queue memory having a plurality of m 32-bit latches 72-1 to 72-m # 2 Is used.
  • the number m of latch stages forming the queue memory # 2 is set to 3
  • the queue memory 72 includes three 32-bit latches 73.74.75.
  • the CPU 61 is connected to the 32-bit data bus 81, and the operation 1 ⁇ 1 63 is also connected to the 32-bit data bus 81.
  • the data of the information word to be input and processed is written to the information word area of the code word buffer ⁇ ⁇ B ⁇ in the working RAM 63 via the 32-bit data bus 81, and the 32-bit data is written from the area. And read to the first input terminal of the 8-bit exclusive-OR units 64, 65, and 66.67.
  • the parity word is extracted from the parity word area of the code word buffer Buf B [] in the working RAM 63 following the data of the information word. And output as a coded code word.
  • FIG. 4 the CPU 61 is connected to the 32-bit data bus 81, and the operation 1 ⁇ 1 63 is also connected to the 32-bit data bus 81.
  • the data of the information word to be input and processed is written to the information word area of the code word buffer ⁇ ⁇ B ⁇ in the working RAM 63 via
  • the 32-bit bus selector 70 converts the 32-bit data input to the a-contact into the 32-bit data input to the b-contact.
  • One of the 32-bit data is selectively output to the CPU 61 and the working RAM 63 via the 32-bit data bus 81.
  • three 32-bit latches 73 and 74.75 that are vertically connected constitute a queue memory 72.
  • the 32-bit latch 73 operates as a latch for writing. Are selected to function as readout latches. Although the selection is physically fixed, the data stored in each 32-bit latch is transferred to the next stage by an operation of writing data to the queue memory 72 or an operation of ejecting data from the queue memory 72. Since it moves to the 32-bit latch, it is not logically fixed, but selects data in the 32-bit latch in order. You.
  • the CPU 61 transmits an input / output address (hereinafter, referred to as an IZO address) to the latch control circuit 62 via an address bus 82 together with an input / output control signal (hereinafter, referred to as an IZO control signal).
  • an IZO address an input / output address
  • the latch control circuit 62 transmits and controls the following control signals to the latches 73, 74, 75, 69 and the bus selector 70 for control.
  • the CPU 61 outputs “AdrsQueue” as an I address to the latch control circuit 62 via the address data bus 82 to the latch control circuit 62, and outputs a “write signal” as the I0 control signal to the latch control circuit. Output to 62.
  • the latch control circuit 62 generates a write clock signal synchronized with the clock CLK and outputs it to the 32-bit latches 73, 74, 75, and 69.
  • the CPU 61 outputs "AdrsQueue” as the I0 address to the latch control circuit 62 via the address data bus 82, and outputs the "readout signal” as the I0 control signal to the latch control circuit. Output to 62.
  • the latch control circuit 62 generates a write clock signal synchronized with the clock CLK and outputs it to the 32-bit latches 73.74 and 75.69.
  • the CPU 61 outputs “Ads Feed” as an I / O address to the latch control circuit 62 via the address data bus 82 and outputs a “write signal” as the I / O 0 control signal to the latch control circuit 62. Output to This is in response to the latch control circuit 62 generates and outputs a harm-out Write-click o click signal synchronized with the clock CLK to 32 bits Toratchi 73. 74. 75 c
  • the CPU 61 outputs “AdsClearPort” as the IZO address to the latch control circuit 62 via the address data bus 82, and outputs the “reduced signal” as the I / O control signal. Output to latch control circuit 62 Power. In response, the latch control circuit 62 outputs a clear signal to the 32-bit latch 69 and clears the data stored in the 32-bit latch 69 to zero.
  • the CPU 61 outputs "Ad rs Queue" as a 1-address to the latch control circuit 62 via the address data bus 82, and outputs an "access signal” as the I / O control signal to the latch control circuit 62.
  • Output to In response, the latch control circuit 62 switches the bus selector 70 to the a contact.
  • the data output from the 32-bit latch 73 is input to the CPU 61 and the working RAM 63 via the a-contact of the bus selector 70 and the 32-bit data bus 81.
  • the CPU 61 outputs “AdrsQueElast” to the latch control circuit 62 as an I address via the address data bus 82, and an “access signal” as an I / O control signal. Is output to the latch control circuit 62. In response, the latch control circuit 62 switches the bus selector 70 to the b contact. As a result, the data output from the 32-bit latch 69 is input to the CPU 61 and the working RAM 63 via the b-contact of the bus selector 70 and the 32-bit data bus 81.
  • FIG. 5 is a flowchart showing an encoding process executed by the CPU 61 of the error correction encoding device of FIG. 3, and FIG. 6 shows an initialization process (step S1) which is a subroutine of FIG.
  • FIG. 7 is a flowchart showing a codeword generation process (step S2) which is a subroutine of FIG.
  • FIG. 8 is a flowchart showing the subroutine process P1 (step S7) of FIG. 7, and
  • FIG. 9 is a flowchart showing the subroutine process P2 (steps S23 and S35) of FIGS. 7 and 8.
  • FIG. 10 is a flowchart showing the subroutine process P 3 (step S37) in FIG. FIG.
  • FIG. 11 is a flowchart showing the subroutine process P 4 (step S 24) of FIG.
  • the program of the control flow of the encoding process shown in FIGS. 5 to 11 is stored in advance in the ROM 61 connected to the CPU 61 in order to operate the error correction encoding device shown in FIGS. 3 and 4. Useful and executed by CPU61.
  • step S1 the initialization processing shown in FIG. 6 is executed in step S1
  • step S2 the codeword generation processing shown in FIG. 7 is executed in step S2
  • [] in the table name and [] in the buffer name represent an array, respectively. If the name of the memory area is n am e, the element of the one-dimensional array is n am e [m] and the element of the two-dimensional array is n ame. [m] [n] where m and n are each an integer of 0 or more. Also, if the size of the array is expressed as nam CM] [N], the valid elements are nam [M-1] [N-1] from nam [0] CO].
  • IOReadW (addres s s) is a function representing a data value read out of 32-bit code data from an IZO address represented by adreresS.
  • IOWriteW (address, data) is a process of saving 32-bit data represented by data to the IO address represented by adreress.
  • GetByte (data, index). Is a function representing the ind Xth byte data from the upper part of the 32-bit code data represented by data. Where i n d e x is a natural number counting from 1.
  • the slash symbol "so" is a binary operator that represents the division of integers
  • AM OD B is a binary operator that calculates the remainder when A is divided by B.
  • AND is a binary operator that performs an AND operation on each bit
  • EOR is a binary operator that performs an exclusive OR operation on each bit.
  • name [x. ⁇ , y] represents the elements from the x-th element to the y-th element of the array n ame.
  • the last one character of the variable name or array name, W.B, represents 32-bit data and 8-bit data, respectively.
  • the Galois field calculation table tGa loi sW [nQu eue Latch] [256] is the data of the product on the Galois field of the input data and each coefficient of the generator polynomial, and is calculated in advance and stored in the ROM 71. Thereafter, during the initialization of the CPU 61 and in the initialization processing accompanying a change in the minimum inter-code distance d of the error correction code, the data is transferred from the ROM 71 to the area in the work RAM 63 and written. In the case where a 12-symbol parity word is added as in the first embodiment, the same data as the contents of the ROM 14 shown in Tables 1 and 2 is stored in the Galois field operation table t GaloisW [nQueu eLayer].
  • t ch] [256] (Step S11).
  • tGa10isW [m] [n] represents the data content of the ROM 14 in the first embodiment where the address H is m and the address L is n.
  • the code word buffer Bu i B [] is a buffer memory set in an area in the working RAM 63, is divided into an information word area and a parity word area, and stores the information word of the code word buffer Bu i B [].
  • the information word to be encoded input before executing this encoding process is stored in advance from the beginning, while in the parity word area of the code word buffer Bu i B [], the information input above is stored.
  • the information word and the parity word are output to an external device as a code word.
  • the ADDRESS Queue Last of the IZO address is an address for reading the contents of the 32-bit latch 73.
  • Table 4 shows that when the error correction coding apparatus S of this embodiment operates according to the flowcharts of FIGS. 5 to 11, the 32-bit latches 73, 74.75, and 69 of FIG. 2 shows stored data.
  • the double underline in Table 4 indicates the scent of the data, and the underline indicates the reading of the data.
  • the symbols of the parity symbols starting from p 000 are the same as those in the first embodiment, and are values calculated by the calculation method of the related art shown in FIG.
  • step S11 in FIG. 6 the Galois field calculation table t G a] 0 i s [n Queue La t ch] [256] is initialized.
  • the contents of the Galois field calculation table t G a 10 is [nQueue Latch] [256] are the first values shown in Tables 1 and 2.
  • the data is transferred from the ROM 71 to the work RAM 63 and initialized so as to have the same data content as the ROM 14 in the embodiment.
  • the 32-bit latches 73, 74, 75, and 69 are cleared to 0. This processing corresponds to step S1001 in Table 4.
  • nFeed nQueueLatch- (nParity-3) Z4 ...
  • the number of feeds nFeed of the queue memory 72 which can be expressed by (31) is calculated and substituted into the number-of-feeds parameter nFeed.
  • the number of 32-bit latches constituting the queue memory 72 is nQueue Latch 3, and the number of parity symbols nPar to be added is 12, so the number of feeds nFeed of the queue memory 72 is 0. Initialized. Then, in step S13,
  • nQ (nParity + 3) /-Queue memory that can be expressed by (32) Is assigned to the number parameter n Q.
  • the number of parity symbols nParity to be added is 12, the number of writes nQ of the queue memory 72 is 3.
  • step S21 of FIG. 7 an information word is picked up from a code word buffer Bu f B [] in the working RAM 63, and a parity word generated by the code word generation processing is created in the queue memory 72. .
  • This treatment is referred to as subroutine treatment P1.
  • step S31 of FIG. 8 the information symbol counter cnt is initialized to 0, and in step S32, the information symbol counter cnt-th 8-bit information symbol B uf B [cnt] is read from the codeword buffer. And input data i nD ata B.
  • the input data i nD ata B is the first symbol of the codeword buffer.
  • the leading information symbol extracted here is i 000 .
  • step S33 32-bit data is read from the 32-bit latch 73, which is an input port, and the index (4th in this case of operation), that is, the lower 8 bits is obtained from the upper bit.
  • the contents of the 32-bit latch 73 are cleared to 00000000H, so the lower 8 bits are 00H.
  • step S34 the contents of the 32-bit latch 69, which is the output port, are cleared to zero. This corresponds to step S1003 in Table 4.
  • step S35 the contents of the queue memory 72 are advanced by the number of feeds nFeed times of the queue memory 72.
  • the data of the 32-bit latch 75 is written to the 32-bit latch 69
  • the data of the 32-bit latch 74 is written to the 32-bit latch 75
  • the data of the 32-bit latch 73 is written to the 32-bit latch 74.
  • to advance by the number of times of feed nFeed times means that the above-described harm process from the latch to the latch is repeated nFeed times.
  • the data of the input port 32 bit latch 73 is stored as it is. This process is referred to as subroutine process P2.
  • step S41 of FIG. 9 the count value cn tFeed of the feed count of the queue memory 72 is initialized to the number of feeds nFeed of the queue 72.
  • the number of feeds nFeed is 0, so the total value cntFeed is 0.
  • step S42 since the count value cnt Feed of the feed counter of the queue memory 72 is 0, the subroutine process P2 ends, and the process returns to the original subroutine process P1 in FIG. That is, in the case of this operation example, nothing is executed in the subroutine process P2.
  • step S33 the exclusive OR of the input data inD ata B and the lower 8-bit data p D ata B of the 32-bit latch 73 obtained in step S33 is obtained, and the data data of the operation result B value d.
  • the input data io is the exclusive OR of the data 00H
  • the data d D Dc of the operation result is expressed by Expression (15), as in the first embodiment.
  • step S37 the product of the data B of the operation result obtained in step S36 and each coefficient of the generator polynomial is read from the Galois field operation table in the working RAM 63, and is read into the queue memory 72. Put in. This processing is referred to as subroutine processing P3.
  • step S51 of FIG. 10 the count value cn tWQ of the queue damage counter is initialized to zero.
  • step S52 the data d obtained in step S36. . .
  • the product of the Galois field of the generator and the coefficient of the generator polynomial (Equation (14)) is read from the Galois field calculation table in the working RAM 63 for 4 symbols (32 bits).
  • k 12 , ku, kio, and k 9 are selected as the coefficients of the generator polynomial (Equation (14)).
  • step S53 the product data on the Galois field read out in step S52 is damaged in the queue memory 72.
  • the 32-bit latch 75 outputs data 00000 000H
  • the 8-bit latch 68 outputs data 00H
  • the input data of the exclusive-OR calculators 64, 65, 66, and 67 are data. Isseki (00H, 00H 00H, 00H. ) and the data (k 12 ⁇ d 000 i ⁇ d ooo kio - dooo k 9 ⁇ dooo...) is. Therefore, exclusive Kazu ⁇ adder 64.65, the output data of 66. 67 (p 000. P 00 i, p 002, p.
  • this data value is expressed by equation (19). be able to. This corresponds to step S 1004 in Table 4.
  • step S54 the count value c n tWQ of the queue write counter is incremented by one. At this time, the count value c n t WQ of the queue write counter becomes 1. Then, in step S55, if the count value cn tWQ of the queue write counter is smaller than the queue damage number nQ, the process returns to step S52. Otherwise, the subroutine process P3 ends and returns. I do. In this case, the count cn tWQ of the queue write counter is 1, and the queue write number nQ is 3, so that the process returns to step S52.
  • step S 52 the product of the Galois field of the coefficients in the obtained data d 00 0 generator polynomial step S 36 (the formula (14)), 4 symbols (32 bits) is determined.
  • the queue one write counter is 1, k e as the coefficient of the generator polynomial (Equation (1 4)), is k 7. K 6. K 5 To be elected.
  • step 52 the product data obtained in step S52 is damaged in the queue memory 72.
  • the 32-bit latch 75 is outputting data OOOO00O0H and the 8-bit latch 68 is outputting data 00H
  • the input data of the exclusive-OR calculators 64, 65. 66, 67 is ( 0OH.
  • step S54 the count value cnt WQ of the queue write counter is incremented by one.
  • the queue damage Cnt WQ is 2.
  • step S55 if the count value cnt WQ of the quenching counter is smaller than the number of queues * nQ, the process returns to step S52, otherwise, the subroutine processing P3 And returns. In this case, since the total number cnt WQ of the queue write counter is 2, and the number nQ of queue writes is 3, the process returns to step S52. ⁇ Then, as in the above process, steps S52 and After passing through step S53 and step S54, the process proceeds to step S55 again. At this time, since the count value cnt WQ of the queue write counter is 3, the subroutine process P3 ends, and the process returns to the subroutine process P1 in FIG.
  • step S38 of FIG. 8 the count value cnt of the information symbol counter is incremented by one. At this time, the count value c nt of the information symbol counter becomes 1. Then, in step S39, if the count value cnt of the information symbol counter is smaller than the number of information symbols nInfo, the process returns to step S32, otherwise, the subroutine process P1 ends and returns. . In this case, the count value c n t of the information symbol counter is 1 and the number of information symbols n I n f o is 20.
  • step S32 the cnt-th information symbol B uf B [cnt] of the information symbol counter is read from the codeword buffer.
  • the count value cnt of the information symbol counter is 1, which is the second symbol from the head of the codeword buffer.
  • the second information symbol read here is i.
  • step S33 32 bits of data are read from the 32 bit latch 73, and the index (4th in the case of this operation example) byte, that is, the lower 8 bits of data is read from the upper bit. obtain.
  • the data in the 32-bit latch 73 is the data (P. 8. P cos. P 0 10. POM), the lower 8 bits of the data are pDU .
  • step S34 the contents of the 32-bit trapping 69 are cleared. This corresponds to step S1008 in Table 4.
  • step S35 the contents of the queue memory 72 are advanced by the number of feeds nFeed times of the queue memory 72.
  • nothing is executed in the subroutine process P2 as in the above-described process.
  • step S36 the exclusive OR of the input data inDataB and the data of the lower 8 bits of the 32-bit latch 73 obtained in step S33 is calculated, and the data value of the calculation result is expressed as d D01 .
  • the input data i. And data p. ,! As in the first embodiment, the operation result data d D (Jl is expressed by equation (16).
  • step S37 the data obtained in step S36 A subroutine process P3, which is a process of damaging the product of the data value and each coefficient of the generator polynomial into the queue memory 72, is executed.
  • step S51 of FIG. 10 the count value cn tWQ of the queue poisoning power counter is initialized to 0, and in step S52, the data d obtained in step S36.
  • the product of the Galois field of cl and the coefficient of the generator polynomial (Equation (14)) is calculated as 4 symbols (32 bits).
  • k 12 as the coefficients of the sometimes count cn TWQ queue harm comes inclusive counter is zero, the generator polynomial (Equation (14)).
  • K ,,. K 10. K e Is selected.
  • step S53 the result data obtained in step S52 is damaged in the queue memory 72.
  • the 32-bit latch 75 is outputting data (Poo. P001. P002, Poos)
  • the input data of the exclusive OR gate 64, 65.66.67 is the data (00H, ⁇ 000. ⁇ . Oo 2 and 7 "* 1 ⁇ (k.12 ⁇ d oDi- k 11 ⁇ d ooi. k) o * aoo, .kg * d 001. Therefore, the output data of the exclusive-OR units 64, 65, 66, 67 Assuming that (P oi2, P 013. P OM, P 015), as in the first embodiment, this data value can be expressed by equation (25), which corresponds to step S 1009 in Table 4. I do.
  • step S54 the count value cntWQ of the queue write counter is incremented by one. At this time, the count value c n tWQ of the queue write counter becomes 1. Further, in step S55, if the count value cn tWQ of the queue writing counter is smaller than the number of queue writes nQ, the process returns to step S52. Otherwise, the subroutine process P3 ends and returns. . In this case, since the count value c n tWQ of the queue entry counter is 1, and the queue entry number n.Q is 3, the process returns to step S52.
  • step S52 four symbols (32 bits) of the product on the Galois field of the data dom obtained in step S36 and the coefficient of the generator polynomial (Equation (14)) are obtained.
  • the Galois field arithmetic table is used, but when the count value cn tWQ of the queue write counter is 1, k e , k 7 , k e , and k 5 are used as coefficients of the generator polynomial (Equation (14)) To be elected.
  • step S53 the result data obtained in step S52 is written in the queue memory # 2.
  • the 32-bit latch 75 stores the data ( ⁇ ⁇ . P 005. P 006.
  • the 8-bit latch 68 is the data ⁇ . . Since 3 is output, the input data of the exclusive OR calculators 64, 65, 66, and 67 are data (P. Q3.P004.PO0S.P006; and data 8 * 0. 1, k 7 * Q 001. k 6 -dooi. k 5 ⁇ do (n). Accordingly, the output data of the exclusive OR calculator 64, 6 5, 66, 67 data (p 0 1 6. P 01 7. P 018. P 01 9 Roh and Then, as in the first embodiment, This data value can be expressed by equation (27), which corresponds to step S1010 in Table 4.
  • step S54 the count value cn tWQ of the queue write counter is incremented by one. At this time, the count cn tWQ of the queue scenting counter becomes 2.
  • step S55 if the count value cnt WQ of the queue write counter is smaller than the queue damage number nQ, the process returns to step S52. Otherwise, the subroutine process P3 ends and returns. In this case, since the count value cn tWQ of the queue damage counter is 2 and the number nQ of queue writes is 3, the process returns to step S52. After that, the process proceeds to step S ⁇ 5 again through steps S52, S53, and S54 in the same manner as the above processing.
  • step S38 of FIG. 8 the count value cnt of the information symbol counter is incremented by one. At this time, the count value c ⁇ ⁇ of the information symbol counter becomes 2.
  • step S39 if the count value cnt of the information symbol counter is smaller than the number of information symbols nInfo, the process returns to step S32, and if not, the subroutine process P1 ends and returns. In this case, since the count value cnt of the information symbol counter is 2, and the number of information symbols nInf0 is 20, the process returns to step S32.
  • step S32 the cnt-th information symbol B u ⁇ B [cnt] of the information symbol counter is read from the codeword buffer.
  • the codeword buffer Is the third symbol from the beginning of The third information symbol extracted here is assumed to be data i aw.
  • step S33 the 32-bit data is read from the 32-bit latch 73, and the index (4th in the case of this example), that is, the lower 8 bits is obtained from the upper bit.
  • 32-bit contents of the Toratchi 73 data P 02D, because it is P 021. P 022. P 023>, the data of the lower 8 bits is p. 23.
  • step S34 the contents of the 32-bit latch 69 of the output port are cleared, which corresponds to step S1013 in Table 4.
  • step S35 the queue memory 72 Is advanced by the number of feeds of the queue memory 72 !! In the same manner as in the above processing, in the present operation example, nothing is executed in the subroutine processing P2.
  • step S36 an exclusive OR of the input data and the data of the lower 8 bits of the 32-bit latch 73 obtained in step S33 is calculated.
  • This data value is d.
  • the data d 002 is represented by Expression (30), as in the first embodiment.
  • the process proceeds to steps S37, S38, and S39, and the count value cnt of the information symbol counter matches the information symbol number nInfo (20 in this operation example).
  • the process from step S32 to step S39 is repeated until the subroutine process P1 is completed, and the process returns to the main routine in FIG.
  • step S22 in FIG. 7 the 32-bit data overflowing from the queue memory 72 is read as dummy data. This corresponds to step S 1102 in Table 4.
  • step S23 the content of the queue memory # 2 is advanced by the number of times n Feed times of the queue memory 72.
  • step S24 a total of n Parity symbols are extracted from the queue memory 72 in units of 4 symbols, and stored in the parity word area of the codeword buffer BufB []. This processing is referred to as subroutine processing P4.
  • step S61 the count value c n t RQ of the queue read counter is initialized to zero.
  • step S62 4 parity symbols are read from the queue memory 72 in units of 4 symbols, and in step S63, the 4 symbols (32 bits) extracted in step S62 are stored in the parity word area of the Yomi word buffer. Is stored.
  • the number of information symbols n I ⁇ ⁇ 0 is 20, and the count value cnt RQ of the queue read counter is 0, so the position to be stored in the codeword buffer B uf B [n I nfo + cn tRQ-4 ....
  • n I nfo + cn tRQ-4 + 3] becomes B u ⁇ B [20,... 23].
  • step S64 the count value cnt RQ of the queue read counter is incremented by one. In this case, the count value cnt RQ is 1.
  • step S65 if the counted value cnt RQ of the queue read counter is smaller than the number of times nQ of writing the queue, the process returns to step S62. Otherwise, the subroutine process P4 is terminated and returned. In this case, the count value cnt RQ is 1 and the queue write cycle Since the number nQ is 3, the process returns to step S62.
  • G) Stores parity symbols for minutes.
  • the number of information symbols n I nfo is 20, and the count value cnt RQ of the queue read counter is 1, so that the position B uf B [n I nf 0 + cnt RQ ⁇ 4, ⁇ , n I nfo + cnt RQ-4 + 3] becomes Bu f B [24.
  • step S64 the count value c n t RQ of the queue read counter is incremented by one. In this case, the count value c n t RQ becomes 2. Further, in step S65, if the count value c n t RQ of the queue read counter is smaller than the number nQ of harmful queues, the process returns to step S62. Otherwise, the subroutine process P4 ends and returns. In this case, the count value c n t RQ is 2, and the number of writes n Q is 3, so that the flow returns to step S62. Thereafter, the processes in steps S62, S63, and S64 are similarly performed, and then the process proceeds to step S65.
  • the subroutine process P4 is terminated and the process returns to the main routine.
  • the above subroutine process P4 corresponds to the processes of steps S1103, S1104, and S1105 in Table 4.
  • the codeword is stored in the codeword buffer Bu ⁇ B [0,-. N I nfo + nParity-1].
  • the number of information symbols nInf0 is 20, and the number of parity symbols nParity is 12, so that the codeword is stored in the codeword buffer BufB [0,..., 31].
  • Table 5 shows the state of each 32-bit latch in FIG. 4 in the present operation example when the error correction coding device operates according to the flowcharts of FIGS.
  • the double underline in Table 5 indicates data writing, and the underline indicates data reading.
  • the symbols starting with 00 are different from the symbols in the first embodiment and the first operation example of the present embodiment, and are values obtained by a calculation method as shown in FIG. In the case of this operation example, the number of information symbols n I nf 0 is 10, and the number of parity symbols n Parity is 5.
  • step S11 in FIG. 6 the Galois field calculation table tGa1ois [nQueueLach] [256] is initialized.
  • the number of 32-bit latches constituting the queue memory 72, nQueueLateh, is 3.
  • the contents of the gamut operation table are initialized to the contents shown in Tables 6 and 7.
  • step S12 the number of feeds nFeed of the queue memory 72 represented by the equation (31) is obtained.
  • the number of 32-bit latches constituting the queue memory 72, n Queue Latch, is 3, and the number of parity symbols to be added, nParity, is 5. Therefore, the number of feeds of the queue memory 72, nFeed, is 1 become.
  • the number of writes nQ of the queue memory 72 represented by the equation (32) is obtained. In the case of this operation example, the number of parity symbols to be added, nParity, is 5, and the number of perfumes, nQ, of the queue memory 72 is 2.
  • step S14 a queue overflow symbol extraction position index that can be expressed by equation (33) is obtained.
  • step S21 in FIG. 7 an information word is read from the code word buffer BufB [] in the work RAM 63, and a subroutine process P1 for creating a parity word on the queue memory 72 is executed.
  • the contents of the subroutine process P1 will be specifically described below with reference to FIG.
  • step S31 of FIG. 8 the count value cnt of the information symbol counter is initialized to zero.
  • step S32 the cnt-th information symbol B uf B [cnt] of the information symbol counter is read from the codeword buffer.
  • the first information symbol read here is data i. Set to 0 o.
  • step S33 32-bit data is read from the 32-bit latch 73, and the index (1st byte in the case of this operation example), that is, the upper 8 bits is obtained from the upper bit.
  • step S34 the contents of the 32-bit latch 69 are cleared to zero. This corresponds to step S2003 in Table 5. Further, in step S35, a subroutine process P2 for advancing the content of the queue memory 72 by the number of times n Feed of the queue memory 72 is executed.
  • step S41 the count value cntFeed of the feed counter of the queue memory 72 is initially set to the number of feeds nFeed of the queue memory 72. Period. In the case of this operation example, since the number of feeds nFeed is 1, the total value cntFeed becomes 1.
  • step S42 if the count value cntFeed of the feed counter of the queue memory 72 is larger than 0, the process proceeds to step S43, otherwise, the subroutine process P2 ends and returns. . In this case, since the count value cIItFeed is 1, the process proceeds to step S43. In step S43, the contents of the queue memory 72 are advanced.
  • step S44 the count value cntFeed of the feed counter of the queue memory 72 is decremented by one. In this case, the count value cnt Feed is 0.
  • step S42 if the count value cntFeed of the feed counter of the queue memory 72 is larger than 0, the process proceeds to step S43. Otherwise, the subroutine process P2 is terminated and the process returns. In this case, since the count value cntFeed is 0, the subroutine process P2 ends, and the process returns to the subroutine process P1 in FIG.
  • step S36 in FIG. 8 the exclusive OR of the input data and the upper 8 bits of the 32-bit latch 73 obtained in step S33 is calculated.
  • this data value a d 000 in this case, since the exclusive OR of the input data io and data 0 0 H, data dooo can be represented by the following equation.
  • step S 37 a subroutine process for writing the product of the data value obtained in step S 36 and each coefficient of the generator polynomial into queue memory 72
  • the subroutine process P3 is specifically described below with reference to FIG.
  • step S51 of FIG. 10 the counter of the queue The value cn tWQ is initialized to 0, and in step S52, the data d no obtained in step S56.
  • the product in the Galois field of the coefficient and the coefficient of the generator polynomial (Equation (34)) is obtained for only 4 symbols (32 bits).
  • k 5 the count value of the generator polynomial (Equation (34)).
  • K 3 k 2 Is chosen.
  • step S53 the data of the result obtained in step S52 is written into the queue memory 72.
  • the input data of the exclusive OR operators 64, 65, 66, and 67 are 00H, 0 OH, 00H, 00H ) and is a data (k s ⁇ dk 3 ⁇ d ooo, k 2 ⁇ d ooo). Therefore, assuming that the output data of the exclusive OR operators 64, 65, 66, 67 is data (p 000 * P DO or P 00 Z.P 003), this data can be expressed by the following equation.
  • step S2005 (k5 * dooo. k4 ⁇ dooo. ks * aooo. k2 ⁇ aooo) ( ⁇ 6) This corresponds to step S2005 in Table 5.
  • step S54 the count value cn tWQ of the queue damage counter is incremented by one. In this case, the count cnt WQ of the queue damage counter becomes 1.
  • step S55 if the count value cn tWQ of the queue write counter is smaller than the queue write number nQ, the process proceeds to step S52, and if not, the subroutine process P3 is terminated and the process returns. In this case, since the count value cn tWQ of the queue scenting counter is 1 and the number of queue writes n Q is 2, the process returns to step S52.
  • step S 52 data d 00 determined in step S 36.
  • step S54 the count value c n t WQ of the queue write counter is incremented by one. In other words, the count value c n tWQ of the queue write counter becomes 2.
  • step S55 if the count value c n tWQ of the queue write counter is smaller than the queue write number nQ, the process returns to step S52. Otherwise, the subroutine process P3 ends and returns. In this case, the count value c n tWQ of the queue entry counter is 2, and the queue write number nQ is 2, so that the subroutine process P3 ends, and the process returns to the subroutine process P1 in FIG.
  • step S38 of FIG. 8 the count value cnt of the information symbol counter is incremented by one. In this case, the information cnt becomes 1.
  • step S39 if the count value cnt of the coasting symbol counter is smaller than the number of information symbols nInfo, the process returns to step S32; otherwise, the subroutine process P1 is ended. Since the count value en ⁇ of the coasting symbol counter is 1 and the number of information symbols n Inf 0 is 10, the process returns to step S32.
  • step S32 the count value cn t-th information symbol of the information symbol counter, ie, BufB [cnt], is read from the codeword buffer.
  • the count value cnt of the information symbol counter is 1, which is the second symbol from the head of the codeword buffer.
  • the second information symbol extracted here is data i 0fll .
  • step S33 32-bit data is read from the 32-bit latch 73, and the index (1st byte in this operation example), that is, the upper 8 bits, is obtained from the upper bit. In this case, the contents of the 32-bit Toratchi 73, data (P 004, 00H.
  • step S34 the contents of the 32-bit latch 69 are cleared to zero. This corresponds to Step S 2008 in Table 5.
  • step S35 a subroutine process P2 for advancing the contents of the queue memory 72 by the number of times n Feed of the queue memory 72 is executed.
  • the key memory 72 is advanced only once in the same manner as the above process. This corresponds to step S2009 in Table 5.
  • step S36 in FIG. 8 the exclusive OR of the input data and the data of the upper 8 bits of the 32-bit latch 73 determined in step S33 is determined. This data value is d. In this case, input data i 0 01 and data! ). Data d because it is exclusive OR with 0 ⁇ . Is expressed by the following equation. Can be.
  • step S37 a subroutine process P3 for writing the product of the data value obtained in step S36 and each coefficient of the generating polynomial into the queue memory 72 is executed.
  • the subroutine process P3 will be specifically described with reference to FIG.
  • step S [delta] 1 of FIG. 10 initializes the count value cn TWQ queue write counter to 0, in step S 52, data d eo determined in step S3 6, a generator polynomial (Equation (34))
  • the product on the Galois field with the coefficient is calculated for only 4 symbols (32 bits).
  • k as the coefficients of the generator polynomial (Equation (34)) s.
  • K 4 . K 3 k 2 Is chosen.
  • step S53 the result data obtained in step S52 is written to the queue memory 72.
  • step S54 the count value cn tWQ of the queue damage counter is incremented by one. In other words, the count cn tWQ of the queue scenting counter becomes 1.
  • step S55 when the count value cnt WQ of the queue entry counter is smaller than the number nQ of queue writes, the process returns to step S52, and otherwise, the subroutine process P3 ends. In this case, the count value cn tWQ of the queue damage counter is 1 and the queue damage number n Q is 2, so that the count goes to step S52.
  • step S ⁇ 2 data d obtained in step S56.
  • data d obtained in step S56 Calculate the product on the Galois field of ( ⁇ and the coefficient of the generator polynomial (Equation (34)) using only 4 symbols (32 bits). In this case, the Galois field arithmetic table is used.
  • the count value cn tWQ is 1, 0, 0.0 is selected as a coefficient of the generator polynomial (Equation (14))
  • step S53 the result data obtained in S52 is stored in the queue memory 72.
  • the 32-bit latch 75 is outputting data (PotH. 0 OH. 0 OH. 00H), and the 8-bit latch 68 is outputting p. 03 .
  • 66, 67 are data (p cos. P 004, 00H, 0 OH) and data (k, d001 , 0 OH. 0 OH. 0 OH. 0 OH). Therefore, if the output data of the exclusive-OR calculators 64, 65. 66, 67 is data (p ooe , P oo *. 0 OH, 00H), the data is data!).
  • ⁇ can be expressed by the following equation.
  • step S54 of FIG. 10 the count cn tWQ of the queue write counter is incremented by one. In other words, cue-in force The count value of the sunset cn tWQ is 2.
  • step S ⁇ 5 when the count value cn tWQ of the queue write counter is smaller than the queue damage nQ, the process returns to step S52. Otherwise, the subroutine process P3 ends and returns.
  • the total number cn tWQ of the queue damage counter is 2, and the number nQ of writes to the queue is 2, so the subroutine process P3 ends, and the process returns to the subroutine process P1 in FIG.
  • step S38 of FIG. 8 the count value cnt of the coast symbol counter is incremented by one. That is, the count value cnt of the information symbol counter becomes 2.
  • step S39 if the count value cnt of the information symbol counter is smaller than the number of information symbols nInfo, the process returns to step S32, otherwise, the subroutine process P1 is terminated and returned. In this case, since the count value cnt of the information symbol counter is 2, and the number of information symbols nInf0 is 10, the process returns to step S32.
  • step S32 the information symbol counter value cnt-th information symbol B uf B [cnt] is read from the code word buffer in the working RAM 63.
  • step S33 the 32-bit data is extracted from the 32-bit latch 73, and the index (1st byte in this operation example), that is, the upper 8-bit data is obtained from the upper bit.
  • the contents of the 32-bit Toratsuchi 73 [p 00 ⁇ , because the p oo4. 0 OH. Is 0 OH) data of the upper 8 bits is P 009. This corresponds to step S2012 in Table 5.
  • step S34 the contents of the 32-bit latch 69 are cleared to zero.
  • step S35 a subroutine process P2 for advancing the contents of the queue memory 72 by the number of times n Feed the queue memory 72 is executed.
  • the queue memory 72 is advanced only once in the same manner as the above process. This corresponds to step S 2014 in Table 5.
  • step S36 of FIG. 8 the exclusive OR of the input data and the data of the upper 8 bits of the 32-bit latch 73 determined in step S33 is determined. If this data value is d tioz, then the input data i. 02 and data P. And the exclusive OR with the data d. 0 2 can be expressed by the following equation.
  • nInfo 10.
  • step S22 of FIG. 7 the 32-bit data overflowing from the queue memory 72 is read as dummy data. This corresponds to step S 2052 in Table 5.
  • step S23 a subroutine process P2 for advancing the contents of the queue memory 72 by nFeed times of the number of feeds of the queue memory 72 is executed.
  • the queue memory 72 is advanced only once, similarly to the above process. This corresponds to step S 2053 in Table 5.
  • step S24 of FIG. 7 a total of n parity symbols are read out from the queue memory 72 for each of the four parity symbols, and A subroutine process P4 for storing in the parity word area of the code word buffer B u ⁇ B [] in the RAM 63 is executed.
  • a subroutine process P4 for storing in the parity word area of the code word buffer B u ⁇ B [] in the RAM 63 is executed.
  • step S61 of FIG. 11 the total value cn tRQ of the queue read count is initialized to 0, and in step S62, parity symbols are read from the queue memory 72 by four symbols. Further steps
  • the parity symbols for 4 symbols (32 bits) read in step S62 are stored in the parity word area of the code word buffer in the working RAM 63.
  • the number of information symbols n Inf 0 is 10
  • the count value cn tRQ of the cue out counter is 0, so the position B uf B [n Inf 0 + cnt RQ to be stored in the codeword buffer ⁇ 4, ⁇ , n I nfo + cn tRQ-4 + 3] becomes Bu f B [10,-, 13].
  • the count value cntRQ of the queue read counter is incremented by one. In this case, the count value c n t RQ becomes 1.
  • step S65 if the count value c n t RQ of the queue ejection counter is smaller than the number nQ of queue writes, the process returns to step S62. Otherwise, the subroutine process P4 ends and returns. In this case, since the count value cn113 ⁇ 40 is 1 and the number nQ of queue writes is 2, the process returns to step S62.
  • step S62 four noble symbols are fired out of the queue memory 72 at a time, and then at step S63, the working RAM
  • the parity symbols for the 4 symbols (32 bits) read in step S62 are stored in the parity word area of the code word buffer in 63.
  • the count value cn tRQ of the queue read counter is 1, the position B uf B [n Info + cn tRQ-4,... N Info + cn tRQ-4 + 3] becomes B uf B [14.
  • the count value cnt RQ of the queue read counter is incremented by one. In this case, the count value cnt RQ is 2.
  • step S65 if the count value cnt RQ of the queue read counter is smaller than the number of times of queue writing nQ, the process returns to step S62. Otherwise, the subroutine process P4 ends and returns. In this case, the count value cnt RQ is 2, and the number nQ of harming the queue is 2, so the subroutine process P4 is terminated and the process returns to the main routine.
  • This subroutine processing P 4 corresponds to steps S 2054 and S 2055 in Table 5.
  • the product data on the Galois field of the input data and each coefficient of the generator polynomial is calculated in advance, stored in the ROM 71, and transferred to the work RAM 63 at the time of initialization processing, and the work RAM 63 constitutes a convenient coefficient storage means. ..
  • the circuit devices shown in FIGS. 3 and 4 are configured so that product data of four symbols can be simultaneously read out from the working RAM 63 serving as coefficient storage means.
  • the first convenient means and the selecting means are realized by using a queue memory 72 composed of m-stage 32-bit latches 72-1 to 72-m, while the second memory is realized by using an 8-bit latch 68. Implement convenient means.
  • the exclusive OR operation means is realized using the other OR calculators 64, 65, 66.67, and the CPU 61 and the latch control device 62 for executing the program stored in the R0M71 are used.
  • read control means and first and second selection means are realized.
  • the minimum inter-symbol distance d can be set freely from 2 to 65.
  • the Galois field calculation table including the product data on the Galois field is transferred from the ROM 71 to the work RAM 63 in the initialization processing and is set, so the seed data to be transferred is changed in the initialization processing.
  • FIG. 15 is a block diagram showing a configuration of the error correction decoding device according to the third embodiment of the present invention. As shown in FIG. 15, the error correction decoding apparatus according to the third embodiment has
  • a reception memory device 213 comprising a shift register in which a plurality of N latches are cascaded.
  • G (X) (X in a flat 0) ( ⁇ - ⁇ 1) ... ( ⁇ - ⁇ 21 - 1) ... (40)
  • the error pattern E at the time of reception is expressed as a sequence of error symbols e,
  • Y (X) y. + y, ⁇ X + y 2 ⁇ X 2 + ... + y n- , ⁇ X n- ] ... (46) Since the received word ⁇ is the codeword ⁇ ⁇ ⁇ to be received plus the error pattern ⁇ , the received polynomial Y (X) is
  • each coefficient r of the remainder polynomial r (X). r i. r 2 ?? r st is expressed by the following equation.
  • the remainder polynomial r (X) is the remainder obtained by dividing the receiving polynomial Y (X) by the generator polynomial G (X).
  • the parity polynomial R (X) which is the remainder obtained by dividing the information polynomial I (X) by the generator polynomial G (X)
  • the error correction encoding device according to the second embodiment can be used as the remainder arithmetic unit 208.
  • the generalized syndrome S (X) can be calculated (for example, see the prior art document "Kiyomichi Araki” et al., "Generalized syndrome for decoding of Reed-Solomon code”). Polynomial ", 1991 IEICE Spring National Convention, A-278, pp. 1-280. 1991.) Therefore, the received word Y is input to the remainder arithmetic unit 208, which is the error correction encoding device according to the second embodiment, and the operation of Expression (52) is performed, whereby the generalized syndrome S CX) is obtained as an output.
  • the remainder arithmetic unit 208 which is the error correction encoding device according to the second embodiment
  • the error value data is While output to the second input terminal of the exclusive OR operator 211, the data at the error position is used as an address in the received word storage device firing controller 210 and the received word description «device scent controller Output to 2 1 2
  • the error value and error position calculator 209 outputs a pair (e in , j n ) of the error value and the error position, and adds the error value e ⁇ ⁇ to the received symbol y located at the error position j ⁇ . This corrects the error.
  • an error position j ⁇ > is input as an address to the received word storage device readout controller 2110 that controls the data read operation of the received word storage device 2 13. Is read from the received word storage device 2 13.
  • the exclusive OR operator 2 1 By inputting the read received symbol y jn and the corresponding error value e in to the exclusive OR operator 2 1 1, the sum of the received symbol y in and the error value e y + e in Is obtained as the output data. Since the output data ye andurbanbecome the corrected code symbol a, the corrected code symbol a in is used as the original error position j n , and the data writing operation of the received word storage device 2 13 is performed. Using the received word storage device damaging controller 2 12 to control the received word storage device 2 13 2.
  • an error correction decoding device can be realized using the error correction encoding device of the second embodiment. Therefore, as in the first and second embodiments, the decoding has a simpler circuit configuration than the prior art device, and can be put to practical use without changing the circuit configuration. It is possible to realize an error correction decoding device that can decode error correction codes having various minimum inter-code distances with high speed. Modified example>
  • the error correction coding device may be configured as follows. That is, the error-correcting coding apparatus according to the modified example has a read having an element on a Galois field GF (2 s ) having an element number of 2 N. Using a Solomon code, a natural number N bits per symbol is obtained. In an error correction encoding device that encodes an error correction code for input data,
  • a plurality of data on the Galois field of each input data and each coefficient of the above-mentioned Reed-Solomon code generator polynomial are respectively calculated in advance, and the above-mentioned plurality of product data is multiplied by b for each address.
  • Product data storage means for storing in advance a set of product data of
  • First storage means comprising a natural number m of storage devices each having a storage capacity of N x b bits;
  • the product data storage means is controlled so that a plurality of harvest data stored in the above-mentioned arena data storage means are read in parallel as a set of a plurality of b harvest data.
  • Read control means
  • Each of them has first and second input terminals of N x b bits, and a plurality of b pieces of product data ejected in parallel from the product data storage means by the read control means are input to the first input terminal. Input to the first input terminal.
  • Exclusive OR operation means for performing an exclusive OR operation on the data and the data inputted to the first input terminal to output data of an operation result;
  • the data stored in the m useful devices is selectively read and output sequentially for each storage device, and the upper Nx (b—b) of the Nx b-bit data selectively read and output is output.
  • Second storage means for temporarily storing data and outputting to the upper N bits of the second input terminal of the exclusive OR operation means
  • the input data is sequentially input to the product data storage means, thereby generating parity data in the m storage devices of the first storage means, and following the input data, the m storages
  • a second selecting means for sequentially outputting the respective parity data generated in the m number of storage devices by selectively switching the devices sequentially for each one of the useful devices.
  • the power of using the ROM 14 to store the harvested data is not limited to this.
  • the present invention is not limited to this, and is configured by a logic circuit using a combination of logic circuit elements instead of the ROM 14, and An arithmetic means for calculating the product data may be used.
  • the present invention has a Galois field GF (2 N) on the original with the original number of 2 N
  • a ROM 14
  • a plurality of product data on the Galois field of each input data and each coefficient of the above-described Reed-Solomon code generator polynomial are calculated in advance, and the above-mentioned plurality of product data is b product data for each address.
  • the read control means (12, 13, 24-26, 28) responds to the input data by combining a plurality of product data recorded in ROM (14) with a set of the plurality of b product data. After reading the data in parallel, the data is selectively written into the natural number m storage devices (20-22) via the exclusive OR operation unit (15-18) and the bus selector (19). By sequentially inputting input data to the ROM (14), parity data is generated and output in the m recording devices.
  • the configuration is such that four product data can be read in parallel (simultaneously) from the ROM 14 storing a plurality of ⁇ data as a set to the exclusive OR operator (15-18), and the four Since the arithmetic operation of the encoding process is performed by simultaneously processing using the product data of the two and selectively using three 32-bit latches (20-22) sequentially and repeatedly, the circuit configuration is It can be extremely simple compared to the circuit configuration of 14 error correction coding devices of the prior art, and can be operated efficiently and at high speed.
  • the error correction code can be encoded at a speed.
  • the circuit configuration can be extremely simplified, and efficient and high-speed operation can be performed.
  • the error correction code can be decoded at a decoding speed that can be put to practical use.

Landscapes

  • Physics & Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Algebra (AREA)
  • General Physics & Mathematics (AREA)
  • Pure & Applied Mathematics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Error Detection And Correction (AREA)
  • Detection And Correction Of Errors (AREA)

Description

明 細 書
淇り訂正符号化装置及び方法、 並びに誤り訂正復号化装 fiS及び方法 術分野
本発明は、 誤り訂正符号化装 及び方法、 並びに誤り IT正復号化装置及 び方法に関する。 特に、 ディジタル記録装置やディジタル通信装置等によつ て、 ディ ジタルデータの記録又は再生、 もしくは、 送信又は受信を行う際 に、 ディジタルデータにおける誤りを訂正する誤り盯正符号を符号化する ための誤り訂正符号化装置及び方法、 並びに、 誤り訂正符号を復号化する ための誤り訂正復号化装置及び方法に関するものである。
背景技術
近年、 ディジタル記録装置やディジタル通信装置の発達に伴い、 ディジ タルデータを記録又は再生する塌合、 もしくは、 送信又は受信する場合に おいて、 ディジタルデータの誤りを如何に少なくするかは、 重要な課題と なっている。 そこで、 ディジタルデータの誤りを訂正するために、 誤り訂 正符号がディジタルデータを取り扱う各種の装 で用いられている。 リ一 ド · ソロモン符号も、 そのような誤り訂正符号の一種であって、 主として、 例えば、 相変化を利用する PDドライブュニッ 卜などのディジタル記録装 置に用いられている。
リード · ソロモン符号は、 符号語が、 元の数が 2 Nであるガロア体 GF (2N) の元から構成され、 なを GF (2N) の原始元としたとき、 生成多 項式が次式で表される多元の巡回ハミング苻号である。
G (X) = (X一な0) (Χ- 1) - CX- 6-2 - (1) ただし、 式 （1) を含めて、 以後、 演算は全てガロア体 GF (2N) 上 で行う。 また、 dは最小符号間距離を表す。
リード · ソロモン苻号の符号語は以下のように生成する。 情報語べク トル Iを次式で表すと、
Figure imgf000004_0001
情報多項式 I (X) は
I (X) = " · X 1 + i , - Xk- 2十… + i 2 ' X+ i - (3) と表すことができる。 ただし、 i 0, i ,, ···, i k-,はそれぞれ惰報シン ボルであり、 情報の元となるビッ トデータについて、 Nビッ トを 1かたま りとして、 ガロア体 GF (2つ 上の元をベク トル表現したものと対応づ ける。
そして、 符号多項式 A (X) は、 情報多項式 I (X) と生成多項式 G (X ) から次式を用いて求めることができる。
A (X) =1 (X) · G (X) … （4) しかしながら、 得られる符号は組織符号にならない。 そこで、 次のよう に符号語を作成する。
まず、 情報多項式 I (X) に Xn_kをかけ、 それを G (X) で割り、 そ の商を Q (X) 、 剰余を R (X) とすると、
I (X) - Xn"k=Q (X) - G (X) +R (X) … （5) と表わすことができる。 ここで、
A (X) =R (X) + I (X) · Χη→ … (6) とおくと、 式 （5) より
A (X) =Q (X) · G (X) … (7) が成立する。 式 （7) によって求められた A (X) は生成多項式 G (X) で割りきれるので、 符号多項式になる。 符号多項式 R (X) を
R (X) - r。 · Xn 1 + r , · Xn-k-2 +…十 - 2 · X十
… (8) で表わすと、 式 （6) で表される符号多項式 A (X) は A (X) = i o · X"-^ i i · X 2十…
+ i κ- 2 · X"-k + ,+ i K · Xn-k
+ rn-い i · Χη·い1 +rn - 2· Χη- 2十… + 7^ · Χ+ r 0
… (9) と表される。 式 （9) の符号多項式で表される符号語をべク トル表現で表 記すると
A= i o. …- i k-i, r o, r ,, …， 10) となり、 式 （10) で表される符号語べク トル Αは、 情報語べク トル Iを そのまま含んでいるから、 組織符号であることがわかる。 この場合、 符号 語べク トル Aは （n, k)組織符号である。 符号語を作成する際に、 情報 語べク トルに付加するべク トル R、 つまり
R= (r0. r！. ···, r„-k -！) … (11) はパリティ語べク トルである。
以上のように生成する符号を、 リード · ソロモン符号 RS (n, k, d = n-k+ 1) と謇く。
図 12にリード · ソロモン符号を用いた従来技術の誤り訂正符号化装置 の一例を示す。 この回路は、 ガロア体 GF (2N) の係数を有する多項式 の除算を行うものである。 図 12において、 誤り訂正符号化装置は、
(a) 8ビッ ト排他的論理和演算器 195乃至 206と、
(b) ガロア体上の係数 k12乃至 を有する係数乗算器 1 Ί 1乃至 18 2と、
(c) 8ビッ トラツチ 183乃至 194と、
( d ) リセッ ト時に 8ビッ トラッチ 183乃至 194の内容を 0にクリア して初期化する初期値設定回路 207とを備える。
当該誤り訂正符号化装置において、 入力データは、 排他的論理和演算器 206の第 1の入力端子に入力され、 排他的論理和演算器 206の出力端 子から出力されるデータは、 係数乗算器 171を介してラッチ 183に入 力されるとともに、 各係数乗 g器 1 Ί 2乃至 183を介してそれぞれ排他 的論理和演算器 195乃至 205に入力される。 さらに、 ラッチ 183乃 至 194と、 排他的論理和演算器 195乃至 206とは、 交互に配置され かつ、 データがラツチ 183からラツチ 194に向かって伝送されるよう に縱铳接続される。
次に、 図 12の誤り IT正符号化装置を用いて実際に 8ビッ トを 1シンポ ルとしたリード ' ソロモン符号 RS (32, 20, d = 13) を符号化す る場合を説明する。
ただし、 原始多項式 m (X) と、 原始元ひと、 生成多項式 G (X) はそ れぞれ以下のように定義する。
m (X) =Χβ + Χ4 + Χ3 + Χ2+1 - (12) α= (00000010) - C13)
G (X)
11
= Π (X -な i)
i = 0
=k】 · Xn+kz · X10 +— +k„ · X + k12 - (1 ) ただし、 式 （14) の k!から k】2は、 生成多 ¾式0 (X) を展開して、 Xの降べきの順に並べたときの、 X11から X。にかかる係数を表す。
第 1の入力データである第 1の惰報シンボル i。。0が排他的論理和演算 器 206に入力されると、 第 1の惰報シンボル i。00と、 8ビッ トラッチ 194の出力データである 00Hとの排他的論理和が演算され、 演算結果 のデータがガロア体係数乗算器 171乃至 182に入力される。 ここで、 00Hの Hは、 16進数表示を表わし、 以下同様である。 この場合におい て、 ガロア体係数乗算器 171乃至 182に入力されるデータを d。00と すると、 第 1の情報シンボル i。00とデータ 00Hとの排他的論理和であ るデータ d00oは、 次式で表わすことができる。
Q ooo= 1 000 "·' (15) これは、 図 13において、 列番号 R 1でかつステップ S 101の 3行分 にある演算に対応する。 次に、 ガロア体係数乗算器 171乃至 182が、 入力データ d oDoとそれぞれの係数 k ! 2乃至 とのガロア体上の穰を出力 する。 これらの積は、 図 13における列番号 R13から R 2まででかつス テツブ S 101の 2行目にあるデータに相当する。
次に、 ガロア体係数乗寞器 171乃至 182の出力データがそれぞれ 8 ビッ トラツチ 183乃至 194に格钠される。 ここで、 各ラッチ 183乃 至 194に格納されるデータをそれぞれ p。D0から Pin,とすると、 これら のデータ値は、 図 13において列番号 R13から R 2まででかつステップ S 101の 3行分にある演算を行った結果に対応する。 ただし、 図 13に おける加算記号は排他的論理和演算を表し、 以下、 演算 E ORは排他的論 理和演算を表す。
次に、 第 2の入力データである第 2の情報シンボル i α«πが排他的論理 和演算器 206に入力されると、 第 2の情報シンボル i。01と、 8ビッ ト ラッチ 194の出力データである Pm】との排他的論理和が演算され、 演 算結果のデータがガロア体係数乗算器 171乃至 182に入力される。 こ の場合、 ガロア体係数乗算器 171乃至 182に入力されるデータを d00
1とすると、 第 2の情報シンボル i DIMとデータ Pm!との排他的論理和で あるデータ d D0 iは次式で表わすことができる。
dDoi = 1 ooi + Poii … (丄 6 ) これは、 図 13において、 列番号 R 2でかつステップ S 101の 3行分 にある濱算に対応する。 次に、 ガロア体係数乗算器 171乃至 182は、 入力データ d001と、 各係数 2乃至 とのガロア体上の積を出力する。 これらの稜は、 図 13における列番号 R 14から R3まででかつステップ S 102の 2行目にあるデータに対応する。
次に、 ガロア体係数乗算器 171乃至 182の出力データがそれぞれ 8 ビッ トラッチ 183乃至 194に格納される。 各ラッチ 183乃至 194 に格納されるデータを P C 1 2から P。23とすると、 これらのデータ値は、 図
13において列番号 R 14から R 3まででかつステップ S 102の 3行分 にある演算を行った結果に対応する。
以下、 同様に、 情報シンボル i。02から愫報シンボル i。19を排他的論理 和澳算器 206に入力していくと、 図 13に示す演算が続けられ、 最後に、 情報語 （i ooo. ioo>. -. i cie) を生成多項式 （式 （14) ) で割つ た余りであるパリティ語 （ρ 22 β, Ρ 229. -, ρ 23 β) がそれぞれ、 8ビッ トラツチ 183乃至 194に格納される。 今まで入力した情報シンボル i
000， 1 001. …， 1 019の続きに、 最後に得られたハリティシンボル P 228.
P 229> ···, P 236を付加すると、 符号語 （ 1 000. 1 001 , ···, 1 01 . P 2 28, P 22Θ. ···· P 239) が C成- S -too
しかしなから、 S112に示すような誤り訂正符号化装置では、 ガロア体 上の係数乗算器 171乃至 182はそれぞれ複雑な回路を有しているため、 最小符号間距離の長い符号を符号化する場合、 大規模な回路となる。 また、 図 12に示すような誤り訂正符号化装置では、 装置の構成を変えずに最小 符号間距離を変更することは、 困難である。 装置の構成を変えずに最小符 号間距離の変更を行うためには、 装置の構成を変えずにガロア体上の係数 乗算器の係数を変更可能にすることと、 装置の構成を変えずに除算回路の ループを変更できる回路にする必要があり、 それらを実現するには、 さら に複雑な回路になる。
本発明の第 1の目的は以上の問題点を解決し、 実用に値する符号化速度 を持ちながら、 従来技術に比較して小規模な回路構成で実現可能であると ともに、 装置の構成を変えずに最小符号間距離 dを自由に変更可能な誤り 訂正符号化装置及び方法を提供することにある。
本発明の第 2の目的は、 実用に値する復号化逨度を持ちながら、 従来技 術に比較して小規模な回路構成で実現可能であるとともに、 装置の構成を 変えずに最小符号間距離 dを自由に変更可能な誤り訂正復号化装置及び方 法を提供することにある。
発明の開示
本発明に係る誤り訂正符号化装匿によれば、 2 Nの元の数を有するガロ ァ体 G F ( 2 N) 上の元を有するリード · ソロモン符号を用いて、 1 シン ボル当たり自然数 Nビッ トの入力データに対する誤り訂正符号を符号化す る誤り訂正符号化装置において、
各入力データと上記リード · ソロモン符号の生成多項式の各係数とのガ ロア体上の複数の種データをそれぞれ予め演算して、 上記複数の積データ を、 各ァドレスに対して複数 b個の穰データを 1組として予め記憶する穫 データ記 ¾手段と、
それぞれ N x bビッ 卜の記悚容量を有する自然数 m個の記憶装置からな る m iの記悌手段と、
入力データに応答して、 上記積データ記憶手段に記億された複数の穣デ 一夕を、 復數 b個の積データを 1組として並列に銃み出すように上記積デ 一夕記憶手段を制御する読み出し制御手段と、
それぞれ N x bビッ トの第 1と第 2の入力端子を有し、 上記読み出し制 御手段によつて上記積データ記憶手段から並列に読み出される複数 b個の 積データが第 1の入力端子に入力され、 上記第 1の入力端子に入力される データと、 上記第 2の入力端子に入力されるデータとの排他的論理和を演 箕して演算結果のデータを出力する排他的論理和澳算手段と、
上記 m個の記慷装置に記悚されたデータを 1つの記憶装置毎に選択的に 順次読み出して出力し、 上記選択的に読み出して出力される N x bビッ 卜 のデータのうち上位 N x ( b— 1 ) ビッ トのデータを上記排他的論理和演 算手段の第 2の入力端子の下位 N x ( b— 1 ) ビッ トに出力するとともに、 上記排他的論理和演算手段から出力される演算結果のデータを、 上記 m個 の記憶装置のうちの 1つに選択的に順次切り換えて害き込むように、 上記 第 1の記憶手段を制御する第 1の選択手段と、
Nビッ 卜の記慷容量を有し、 上記第 1の選択手段によって上記 m個の記 憶装置のうちの 1つから選択的に出力される N x bビッ 卜のデータのうち 下位 Nビッ トのデータを一時的に記使して上記排他的論理和演算手段の第 2の入力端子の上位 Nビッ 卜に出力する第 2の記憶手段と、
上記入力データを上記稷データ記憶手段に順次入力することにより、 上 記第 1の記慷手段の m個の記慷装置においてパリティデータを生成し、 上 記入力データに続いて、 上記 m個の記憧装慝を 1つの記慷装置毎に選択的 に順次切り換えることにより、 上記 m個の記使装置において生成される各 パリティデータを順次出力する第 2の選択手段とを備えたことを特徴とす る。.
また、 上記誤り訂正符号化装置において、 好ましくは、 上記読み出し制 御手段と、 上記第 1の選択手段と、 上記第 2の選択手段とは、 別の記憶装 置に記億された所定のプログラムを実行する中央演算制御装置によって構 St 3れる。 また、 本発明に係る誤り訂正復号化装置によれば、 2 Nの元の数を有す るガロア体 G F ( 2 N) 上の元を有するリード ' ソロモン符号を用いて、 1 シンボル当たり自然数 Nビッ 卜の入力データに対して符号化された誤り 訂正符号を復号化する誤り訂正復号化装置において、
上記入力データと、 上記入力データに対するパリティデータとを含む複 数の受信シンボルからなり、 入力される受信語を各受信シンボル毎に記憶 する受信語記憶手段と、
上記誤り訂正符号化装置を備え、 上記リード · ソロモン符号の生成多項 式を用いて、 上記入力される受信語に対する剰余を演算して出力する剰余 演算手段と、
上記剰余演算手段から出力される剰余に基づいて、 上記受信語における 誤り位置と、 上記誤り位 Sに対応する誤り数値との組を演算して出力する 誤り数値及び誤り位置演算手段と、
上記誤り数値及び誤り位置演算手段から出力される上記受信語における 誤り位置に基づいて、 上記受信語記慷手段に記憶された上記誤り位置にお ける受信シンボルを上記受信語記憶手段から読み出して出力する読み出し 制御手段と、
上記読み出し制御手段から出力される上記誤り位置における受信シンボ ルと、 上記誤り数値及び誤り位置演算手段から出力される、 上記誤り位置 に対応する誤り数値との排他的論理和を演算して、 演算桔果のデータを出 力する排他的論理和演算手段と、
上記排他的論理和演算手段から出力される演算結臬のデ一夕を、 上記受 信語記憶手段の上記誤り位置に窨き込むことにより、 上記誤り位置におけ る受信シンボルを訂正する香き込み制御手段とを備えたことを特徴とする。 さらに、 本発明に係る誤り訂正符号化方法によれば、 2 Nの元の数を有 するガロア体 G F ( 2 N) 上の元を有するリード . ソロモン符号を用いて、 1シンボル当たり自然数 Nビッ 卜の入力データに対する誤り訂正符号を符 号化する誤り訂正符号化方法において、
各入力データと上記リード ' ソロモン符号の生成多項式の各係数とのガ ロア体上の複数の積データをそれぞれ予め演算して、 上記複数の積データ を、 各ァドレスに対して複数 b個の積データを 1組として積データ記憶手 段に予め記憶するステップと、
入力データに応答して、 上記積データ記憶手段に記慷された複数の積デ 一夕を、 複数 b個の積データを 1組として並列に読み出すように上記積デ ータ記憶手段を制御するステップと、
それぞれ N x bビッ 卜の第 1と第 2の入力端子を有する排他的論理和演 算手段を用いて、 上記積データ記憶手段から並列に読み出される複数 b個 の稜データが第 1の入力端子に入力され、 上記第 1の入力端子に入力され るデータと、 上記第 2の入力端子に入力されるデータとの排他的論理和を 演算して演算結果のデータを出力するステップと、
それぞれ N X bビッ トの記悚容量を有する m個の記憶装置の第 1の記憶 手段に記慷されたデータを 1つの記億装置毎に選択的に順次読み出して出 力し、 上記選択的に銃み出して出力される N x bビッ 卜のデータのうち上 位 N x ( b— 1 ) ビッ トのデータを上記排他的論理和演算手段の第 2の入 力端子の下位 N x ( b— 1 ) ビッ トに出力するとともに、 上記排他的論理 和演算手段から出力される演算結果のデータを、 上記 m個の記悚装置のう ちの 1つに選択的に順次切り換えて書き込むように、 上記第 1の記慷手段 を制御するステップと、
Nビッ 卜の記懞容量を有する第 2の記憶手段を用いて、 上記 m個の記慷 装置のうちの 1つから選択的に出力される N x bビッ トのデータのうち下 位 Nビッ トのデータを一時的に記憶して上記排他的論理和演算手段の第 2 の入力端子の上位 Nビッ トに出力するステップと、
上記入力データを上記積データ記憶手段に順次入力することにより、 上 記第 1の記慷手段の m個の記憶装置においてパリティデータを生成し、 上 記入力データに铳いて、 上記 m個の記億装置を 1つの記憶装置毎に選択的 に順次切り換えることにより、 上記 m個の記憶装置において生成される各 パリティデータを順次出力するステップとを含むことを特徴とする。
またさらに、 本発明に係る誤り訂正復号化方法によれば、 2 Nの元の数 を有するガロア体 G F ( 2 N) 上の元を有するリード . ソロモン符号を用 いて、 1 シンボル当たり自然数 Nビッ 卜の入力データに対して符号化され た誤り訂正符号を復号化する誤り訂正復号化方法において、
上記入力データと、 上記入力データに対するパリティデータとを含む複 数の受信シンボルからなり、 入力される受信語を各受信シンボル毎に受信 語記憶手段に記億するステップと、
上記誤り訂正符号化方法により、 上記リード， ソロモン符号の生成多項 式を用いて、 上記入力される受信語に対する剰余を演算して出力するステツ ブと、
上記出力される剰余に基づいて、 上記受信語における誤り位置と、 上記 誤り位置に対応する誤り数値との組を演算して出力するステップと
上記出力される上記受信語における誤り位置に基づいて、 上記受信語記 憧手段に記悚された上記誤り位置における受信シンボルを上記受信語記憶 手段から読み出して出力するステップと、
上記出力される上記誤り位置における受信シンボルと、 上記出力される、 上記誤り位置に対応する誤り数値との排他的論理和を演算して、 演算結果 のデータを出力するステップと、 上記出力される演算桔果のデータを、 上記受信語記慷手段の上記誤り位 置に香き込むことにより、 上記誤り位置における受信シンボルを訂正する ステップとを含むことを特徴とする。
図面の簡単な説明
図 1は、 本発明に係る第 1の実施形態の誤り訂正符号化装置のプロック 図である。
図 2は、 図 1の誤り訂正符号化装置の動作を示すタイミ ングチャートで あ 0
図 3は、 本発明に係る第 2の実施形態の誤り訂正符号化装置のプロック 図である。
図 4は、 図 4の誤り訂正符号化装置において m= 3としたときのブロッ ク図である。
図 5は、 図 3の誤り訂正符号化装 の CPU61によって実行される符 号化処理を示すフローチヤ一トである。
図 6は、 図 5のサブルーチンである初期化処理 （ステップ S 1) を示す フローチヤ一トである。
図 7は、 図 5のサブルーチンである符号語生成処理 （ステップ S 2) を 示すフローチヤ一トである。
図 8は、 図 7のサブルーチン処理 P 1 (ステップ S7) を示すフローチヤ 一トである。
は、 図 7及び図 8のサブルーチン処理 P 2 (ステップ S 23, S3 5) を示すフローチヤ一トである。
図 10は、 図 8のサブルーチン処理 P 3 (ステップ S37) を示すフロ 一チヤ一トである。
図 11は、 図 7のサブルーチン処理 P 4 (ステップ S 24) を示すフロ 一チヤ一トである。
図 12は、 従来技術の誤り訂正符号化装置のブロック図である。
図 13は、 図 12の誤り訂正符号化装置においてリ一ド · ソロモン符号 RS (n. n— 12, d = 13 ) の計算方法を説明するための図である。 図 14は、 図 12の誤り訂正符号化装置においてリード · ソロモン符号 RS (n. n-5, d = 6) の計算方法を説明するための図である。
図 15は、 本発明に係る第 3の実施形態の誤り訂正復号化装置のプロッ ク図である。
発明を実施するための最良の形態
以下、 本発明に係る実施形態について図面を参照して説明する。
<第 1の実施形態〉
本発明に係る笫 1の実施形態について、 図面を参照しながら説明する。 第 1の実施形態では、 8ビッ トを 1シンボルとしたリード · ソロモン符号 RS (32. 20. d= 13) を符号化する埸合を説明する。 ただし、 原 始多項式 m (X) 、 原始元 α、 生成多項式 G (X) はそれぞれ式 （12) 、 式 （13) 、 式 （14) のように定義する。
図 1は、 本発明に係る第 1の実施形態の誤り訂正符号化装置の稱成を示 すブロック図である。 この第 1の実施形態の誤り ΓΓ正符号化装置は、
(a) 8ビッ トラツチ 12, 27と、
(b) 4進カウンタ 13と、
(c) ROM (読み出し専用メモリ） 14と、
(d) 8ビッ ト排他的論理和演算器 11. 15. 16. 17. 18と、
(e) 32ビッ トバス選択器 19. 23と、
(f ) 32ビッ トラッチ 20. 21. 22からなるキューメモリ 30と、
(g) 入力データ "1" をデコードしてパルス信号を出力するデコーダ 2 4と、
(h)入力データ "2" をデコードしてパルス信号を出力するデコーダ 2 5と、
(i)入力データ "3" をデコードしてパルス信号を出力するデコーダ 2 6と、
( j ) 入力データ "0" をデコー ドしてパルス信号を出力するデコーダ 2 8と、
(k) 2ビッ トラツチ 29と、
( 1 ) 3個のシンボル遅延回路 301乃至 303からなる遅延回路 300
(m) 8ビッ ト出力データ選択器 310とを備える。
図 1の誤り訂正符号化装置において、 8ビッ 卜の入力データは、 排他的 論理和演算器 11の第 1の入力端子に入力されるとともに、 出力データ選 択器 310の d接点を介して出力データとして出力される。 排他的論理和 演算器 18の出力端子からの出力データは、 排他的論理和澳算器 11の第 2の入力端子に入力される。 一方、 クロック CLKは、 4進カウンタ 13 と、 ラッチ 29及び 27に入力される。 4進カウンタ 13は、 入力される クロック CLKを計数し、 かつ計数値が 4となると 0にリセッ 卜し、 その 計数値の 2ビッ トのデータを、 ラツチ 29を介して上位 2ビッ トのァドレ スとして ROM14のァドレス端子に出力するとともに、 選択信号として バス選択器 19. 23及びデコーダ 20, 21. 22, 28に出力する。 ここで、 2ビッ トラッチ 29は、 4進カウンタ 13の計数値の 2ビッ トデ 一夕を、 クロック CLKの立ち下がりのタイミングでラツチする。
デコーダ 28は、 4進カウンタ 13の出力データが "0" の値を示した とき、 クロック C LKの半周期の時間だけ遅れてク πック C LKの半周期 の幅を有するパルス信号をラッチ 27に出力する。 また、 デコーダ 24は、 4進カウンタ 13の出力データが "1" の値を示したとき、 クロック CL Kの半周期の時間だけ遅れてクロック CLKの半周期の幅を有するパルス 信号をラッチ 20に出力する。 さらに、 デコーダ 25は、 4進カウンタ 1 3の出力データが "2" の値を示したとき、 クロック CJLKの半周期の時 間だけ遅れてクロック C LKの半周期の幅を有するパルス信号をラツチ 2 1に出力する。 またさらに、 デコーダ 26は、 4進カウンタ 13の出力デ 一夕が "3" の値を示したとき、 クロック CLKの半周期の時間だけ遅れ てクロック C L Kの半周期の幅を有するパルス信号をラツチ 22に出力す る。
ここで、 8ビッ トラッチ 12は、 排他的論理和演算器 11からの 8ビッ トデータを、 デコーダ 26からのパルス信号のクロック CLKの立ち上が りのタイミングでラッチして ROM14に下位 8ビッ 卜のァ ドレスとして 出力する。 ROM14には、 べク トル表現の入力シンボルに対して所定の 係数をガロア体上で乗算した桔果がべク トル表現で予め格納されている。 入力データはァドレスの下位 8ビッ トとして与え、 ァドレスの上位 2ビッ トは係数を切り替えるために用いる。 ROM14のデータ端子からの 32 ビッ トの出力データは、 4個の排他的論理和演算器 15乃至 18の第 1の 入力端子に入力され、 その出力端子から出力される 32ビッ 卜のデータは、 32ビッ トバス選択器 19の入力端子に入力される。 また、 排他的論理和 澳算器 18から出力される 8ビッ トの出力データは排他的論理和演算器 1 1の第 2の入力端子に入力される。
ここで、 32ビッ トバス選択器 19, 23はそれぞれ、 8ビッ トバス 4 本分を連動して 4回路に切り替えるバス選択器である。 32ビッ 卜バス選 択器 19. 23は、 選択信号が " 0" のとき最下位置の d接点に切り換え られて、 バス：！択器 1 9の入力端子及びバス選択器 2 3の出力端子はそれ ぞれオープン状態となる。 また、 3 2ビッ トバス選択器 1 9 , 2 3は、 選 択信号が " 1 " のとき最上位置の a接点に切り換えられて、 バス選択器 1 9の入力端子は 3 2ビッ トラツチ 2 0の入力バスに接続されるとともに、 バス選択器 2 3は 3 2ビッ トラツチ 2 0の出力バスに接続される。 さらに、 3 2ビッ トバス選択器 1 9. 2 3は、 選択信号が " 2 " のとき最上から 2 番目の位置の b接点に切り換えられて、 バス選択器 1 9の入力端子は 3 2 ビッ トラツチ 2 1の入力バスに接続されるとともに、 バス選択器 2 3は 3 2ビッ トラツチ 2 1の出力バスに接続される。 またさらに、 3 2ビッ トバ ス選択器 1 9， 2 3は、 選択信号が " 3 " のとき最上から 3番目の位置の c接点に切り換えられて、 バス選択器 1 9の入力端子は 3 2ビッ トラツチ 2 2の入力バスに接続されるとともに、 バス選択器 2 3は 3 2ビッ トラッ チ 2 2の出力バスに接続される。
バス選択器 2 3から出力される 3 2ビッ 卜の出力データのうち上位 2 4 ビッ トのデータは、 排他的論理和演算器 1 7 . 1 8 , 1 9の第 2の入力端 子に入力され、 バス選択器 2 3から出力される 3 2ビッ トの出力データの うち下位 8ビッ トめデータは、 8ビッ トラツチ 2 7を介して、 排他的論理 和演算器 1 5の笫 2の入力端子に入力される。 ここで、 8ビッ トラッチ 2 7は、 入力される 8ビッ 卜のデータを、 クロック C L Kの立ち上がりの夕 ィミングでラツチした後、 排他的論理和演算器 1 5の第 2の入力端子に出 力し、 デコーダ 2 8からのパルス信号に応答して、 ラッチしているデータ を 0にクリアする。
3 2ビッ トラツチ 2 0から出力される 3 2ビッ 卜の出力データはシンポ ル遅延回路 3 0 1に入力され、 シンボル遅延回路 3 0 1は、 入力される 3 2ビッ 卜のデータのうち ( a ) 上位 8ビッ トデータを、 バス選択器 3 1 0の a接点から出力される 惰報シンボルの後に、 遅延することなく 8ビッ 卜バス選択器 3 1 0の b接 点を介して出力データとして出力し （以下、 この出力データの出カタイミ ングを基準出力タイミングという。 ） 、
( b ) 次の上位 8ビッ 卜データを上記基準出カタイミ ングから 1シンボル (= 1バイ ト == 8ビッ 卜） だけ遅延した後、 8ビッ トバス選択器 3 1 0の b接点を介して出力データとして出力し、
( c ) 次の上位 8ビッ トデータを上記基準出力タイミングから 2シンボル だけ遅延した後、 8ビッ 卜バス選択器 3 1 0の b接点を介して出力データ として出力し、
( d ) 次の下位 8ビッ トデータを上記基準出力タイミングから 3シンボル だけ遅廷した後、 8ビッ トバス選択器 3 1 0の b接点を介して出力データ として出力する。
また、 3 2ビッ トラツチ 2 1から出力される 3 2ビッ 卜の出力データは シンボル遅延回路 3 0 2に入力され、 シンボル遅延回路 3 0 2は、 入力さ れる 3 2ビッ トのデータのうち
( a ) 上位 8ビッ トデータを上記基準出力タイミングから 4シンボルだけ 遅延した後、 8ビッ 卜バス選択器 3 1 0の c接点を介して出力データとし て出力し、
( b ) 次の上位 8ビッ トデータを上記基準出力タイミングから 5シンボル だけ遅延した後、 8ビッ トバス選択器 3 1 0の c接点を介して出力データ として出力し、
( c ) 次の上位 8ビッ トデータを上記基準出力タイミングから 6 シンボル だけ遅延した後、 8ビッ トバス選択器 3 1 0の c接点を介して出力データ として出力し、 ( d ) 次の下位 8ビッ トデータを上記基準出力タイミ ングから 7シンボル だけ遅延した後、 8ビッ トバス選択器 3 1 0の c接点を介して出力データ として出力する。
さらに、 3 2ビッ トラッチ 2 2から出力される 3 2ビッ 卜の出力データ はシンボル遅延回路 3 0 3に入力され、 シンボル遅延回路 3 0 3は、 入力 される 3 2ビッ 卜のデータのうち
( a ) 上位 8ビッ トデータを上記基準出力タイミングから 8シンボルだけ 遅延した後、 8ビッ トバス選択器 3 1 0の d接点を介して出力データとし て出力し、
( b ) 次の上位 8ビッ トデータを上記基準出力タイ ミングから 9シンボル だけ遅延した後、 8ビッ 卜バス選択器 3 1 0の d接点を介して出力データ として出力し、
( c ) 次の上位 8ビッ トデータを上記基準出力タイ ミングから 1 0シンポ ルだけ遅延した後、 8ビッ 卜バス選択器 3 1 0の d接点を介して出力デ一 タとして出力し、
( d ) 次の下位 8ビッ トデータを上記基準出力タイミングから 1 1シンポ ルだけ遅延した後、 8ビッ トバス選択器 3 1 0の d接点を介して出力デ一 タとして出力する。
従って、 当該誤り訂正符号化装置に入力される、 例えば 2 0シンボルの 情報シンボルに統いて、 誤り訂正符号化されラツチ 2 0に格納された 3 2 ビッ ト = 4シンボルのパリティ語と、 誤り訂正符号化されラッチ 2 1に格 納された 3 2ビッ ト = 4シンボルのパリティ語と、 誤り訂正符号化されラッ チ 2 2に格納された 3 2ビッ ト = 4シンボルのパリティ語とが出力データ としてバス：！択器 3 1 0から出力される。
図 2は、 図 1の誤り訂正符号化装置の動作を示すタイミ ングチャー トで ある。 入力データは 8ビッ 卜で、 クロック C LKの 4個のパルスにつき 1 度入力される。 また、 4進カウンタ 13の初期値は 2に設定され、 8ビッ トラツチ 12， 27、 32ビッ トラッチ 20, 21, 22の初期値は 0に 設定され、 2ビッ トラッチ 29の初期値は 0に設定される。
表 1及び表 2は、 ROM14に記憶されるデータの内容である。 表 1及 び表 2において、 乃至 k】2は式 （14) に示す生成多項式 G (X) の 係数であり、 なは式 （13) に示すガロア体 GF (28) の原始元であり、 積の記号はガロア体上の積を表す。 な n (ここで、 mは 1から 12ま での自然数であり、 nは 0以上の整数である。 ） はどちらもガロア体 GF (28) の元である。 従って、 と との積もガロア体 GF (28) の元 であり、 ベク トル表現を用いると 8ビッ トの数値に対応するので、 その積 の数値データは ROM14に予め格納される。
表 1及び表 2において、 アドレス Ηは、 ROM 14の上位 2ビッ トのァ ドレスであり、 ァ ドレス Lは ROM 14の下位 8ビッ トのァ ドレスである。 また、 b [31， ···， 24] は最上位 8ビッ トの係数データであり、 b [2 3. ···, 16] は次の上位 8ビッ トの係数データであり、 b [15, …， 8] は次の上位 8ビッ トの係数データであり、 b 〔7， ·■·, 0] は最下位 8ビッ トの係数データである。
表 3はガロア体 GF (28)上の元をべク トル表現からべき表現に変換 するための変換表である。 表 3は参考のために記載したものであり、 本実 施形態において直接用いるデータではない。 表 3から明らかなように、 表 1及び表 2に示す ROM 14のァドレス Lのデータ値をべき表現に変換す れば、 そのアドレスに害かれている値の αη (ここで、 ηは 0以上の整数 である。 ） の部分に対応することがわかる。 従って、 ROM14において、 例えばァ ドレス Ηに 0を入力し、 ァ ドレス Lにべク トル表現 （8ビッ ト） のガロア体 GF (28) の元を入力すると、 ROM14は生成多項式の係 数 k . k . k,0, keとアドレス Lに入力した値のガロア体上の積を 出力することがわかる。
(以下余白）
表
Figure imgf000023_0001
表 2
Figure imgf000024_0001
表 3
Figure imgf000025_0001
以下、 図 2を参照して図 1の誤り訂正符号化装置における誤り符号化処 理について説明する。
まず、 第 1番目のクロック CLKの立ち下がりと同期するデコーダ 26 の出力パルス信号の立ち上がりにおいて、 32ビッ トバス選択器 19. 2 3は 32ビッ トラツチ 22を選択している。 このとき、 8ビッ 卜排他的論 理和演算器 18の入力データは、 ROM14の出力データの下位 8ビッ ト であるデータ 00Ηと、 32ビッ トラツチ 22の出力データの第 16ビッ トから第 9ビッ 卜にあたるデータ 00Hであるから、 8ビッ 卜排他的論理 和演算器 18の出力データは 00Hになる。 そのため、 8ビッ ト排他的論 理和演算器 11の入力データは、 8ビッ ト排他的論理和演算器 18の出力 データであるデータ 00 Hと、 入力データ i oとになり、 8ビッ トラッ チ 12にはデータ i。00が格納される。 従って、 図 2のデータ d D0[lは式 （1 5) によって表わすことができる。 これと同時に、 8ビッ トラツチ 27の 出力データと、 ROM14の出力データの上位 8ビッ 卜の排他的論理和の データを 8ビッ ト排他的論理和演算器 15が出力しており、 また 32ビッ トラツチ 22の出力データの上位 24ビッ トと、 ROM 14の出力データ の下位 24ビッ トとの排他的論理和の 24ビッ 卜のデータを gビッ ト排他 的論理和演算器 16, 17, 18が出力している。 従って、 以上の 4個の 8ビッ ト排他的論理和演算器 15, 16, 17, 18の出力データは 32 ビッ トラツチ 22に害き込まれる。 また、 それと同時に 8ビッ トラツチ 2 7には、 以前 32ビッ トラツチ 22に書き込まれていたデータの下位 8ビッ 卜が書き込まれる。 この場合、 8ビッ ト排他的論理和演算器 15. 16. 17. 18の各 8ビッ トの入力データが全て 00Hであるので、 32ビッ トラツチ 22に書き込まれるデータは 00000000Hである。 また、 8ビッ トラッチ 27に香き込まれるデータは 00Hである。 以上の動作の 後に、 ROM14に与えられるァドレスの下位 8ビッ トは d。00になり、 その上位 2ビッ トは "3" になる。 ここで、 ROM 14には表 1に示すよ うなデータか格納されており、 ガロア体上の積の演算をテーブル参照で求 めることができる。 この場合、 ァドレスの上位 2ビッ トは "3" であるの で、 ROM14はそのデータ端子からデータ 00000000Hを出力す る。 従って、 図 2の ROM 14の出力データ A Dを 8ビッ トずつ区切って 表現すると、 次式で表わすことができる。 Ao= (0 OH. 0 OH. 0 OH. 0 OH) - (17) 次に、 第 2番目のクロック CLKの立ち下がりと同期するデコーダ 28 の出力パルス信号の立ち上がりにおいて、 8ビッ トラッチ 27が 0にクリ ァされる。 また、 ROM 14に与えられるア ドレスの下位 8ビッ トはデー タ dD0Dのまま変わらず、 その上位 2ビッ トは '0" になるため、 表 1よ り図 2の ROM 14の出力データ A！は次式で表わすことができる。
Aa = ( k 12 · d 000, k lo♦ d ooo. k 9 - Q o o D)
··· (18) ただし、 積の記号 はガロア体上の積の演算を意味する。
次に、 第 3番目のクロック C LKの立ち下がりと同期するデコーダ 24 の出力信号の立ち上がりにおいて、 32ビッ トバス選択器 19. 23は 3 2ビッ トラッチ 20を選択している。 このとき、 8ビッ トラッチ 27の 8 ビッ 卜の出力データと、 ROM14の出力データの上位 8ビッ 卜の排他的 論理和のデータを 8ビッ ト排他的論理和演算器 15が出力しており、 また 32ビッ トラツチ 20の出力データの上位 24ビッ トと、 ROM14の出 力データの下位 24ビッ 卜との排他的論理和のデータを 8ビッ 卜排他的論 理和演算器 16. 17, 18が出力している。 従って、 以上の 8ビッ ト排 他的論理和演算器 15. 16. 17, 18の 32ビッ トの出力データは、 32ビッ 卜ラッチ 20に害き込まれる。 また、 それと同時に 8ビッ トラッ チ 27には、 以前 32ビッ トラツチ 20にさき込まれていたデータの下位 8ビッ トが書き込まれる。 この場合、 8ビッ トラッチ 27の出力データは データ 00 Hであり、 また 32ビッ トラツチ 20の出力データの上位 24 ビッ トもデータ 000000Hであるので、 32ビッ トラッチ 20に害き 込まれるデータは式 （18) で表されるデータ そのものである。 従つ て、 図 2の 32ビッ トラッチ 20の出力データである （P ooo. οοι. ρ 002， P 003 ) は次式で表わすことができる。
( P 000, P 001 > P 002, P 0 oa)
― ( k 1 2 ' a o o o» k 1 1 · a ooo. k ι o · Q oo o» kg · d ooo)
··· (1 9) また、 8ビッ トラッチ 2 7に窨き込まれるデータはデータ 00 Hである。 上の動作の後に、 ROM1 4に与えられるァドレスの下位 8ビッ トはデ ータ d ooDとなり、 その上位 2ビッ トは "1" になる。 従って、 図 2の R OM 1 4の出力データ A 2は次式で表わすことができる。
A 2 = (ke * α ooo. k 7 · Q ooo> k 6 · d 0oo. k 5 - α。ο。)
… (20) 同様にして、 データ （Ρθ(Μ. Ρ 005. Ρ 006> oo?) は次式で表わすこ とができる。
( P 004. P 005. P 006. P 007 )
= ( k 8 · d ooo. k 7 · a ooo. k 6 · □ ooo. k 5 * a ooo) -.. (2 1ノ また、 ROM1 4の出力データ A 3は次式で表わすことができる。
A3= (k4 · d 000， k3 · d 000. k2 · d ooo. k i · d ooo)
… （22) また、 データ （P 008, P 009. P 01 0. P O i l ) は次式で表わすことがで きる。
( P 008· P 009ι P 01 0· Ρθΐΐ)
= (k * dooo. k 3 · d oo o. k 2 * a o o o. k i · u ooo) ··· ( 3) ただし、 第 5番目のクロック C LKの立ち下がりと同期して 8ビッ トラッ チ 1 2の出力データが変化する。 具体的にはデコーダ 26の出力パルス信 号の立ち上がりにおいて、 32ビッ トバス選択器 1 9, 2 3が 3 2ビッ ト ラッチ 22を選択しているため、 第 1番目のクロック C LKの時と同様に、 8ビッ ト排他的論理和演算器 11の入力データは 8ビッ ト排他的論理和演 算器 18の出力データである P ouと、 入力データ i 001になり、 8ビッ ト ラッチ 12には、 式 （15) で表されるデータ d。。，が格納される。 ただ し、 式 （15) において和の記号はガロア体上の和の演算を意味する。 次に、 第 7番目のクロック CLKの立ち下がりと同期するデコーダ 24 の出力信号の立ち上がりにおける状態を説明する。 このとき、 32ビッ ト バス選択器 19, 23は 32ビッ 卜ラッチ 20を選択している。 上記の処 理と同様に考えると、 8ビッ トラッチ 27の出力データは 00Hであり、 また 32ビッ トラッチ 20の出力データの上位 2 ビッ トは、
( P 000. Ρ οοι, 002)
= (k 12 · □ 000. k n · α οοο- k i ο · α 000) ··· (24) であるので、
( 012. Ρ 013. Ρ 01 . Ρ 01 δ)
= ( k 12 ' d 001. k 11 · d ooi"t" P ooo.
k.10 · d.001 + P 001. k 9 · d 001 + p 002)
= ( k 12 · d 001. k 11 · d 001 + k 12 · d ooo> k 10 ■ d 001
+ k 11 · d 000. k 9 · d ooi + k 10 · d 000) ··· (25) で表されるデータが 32ビッ トラツチ 20に香き込まれる。
また、 32ビッ トラツチ 20の害き込み前のデータ値の下位 8ビッ 卜で あるデータ p。03が同時に 8ビッ トラッチ 27に者き込まれる。 以上の動 作の後に、 ROM14に与えられるァドレスの下位 8ビッ トはデータ d00 jとなり、 その上位 2ビッ トは "1" になる。
従って、 図 2の ROM14の出力データ B2は、 次式で表わすことがで さる。
B 2= ( k 8 · α 001. k 7 · α 001. k 6 · α ooi . k 5 · d ooi ) C26)
(以下余白）
同様にして、 データ （P 016, P 017, P 018. P 019) は次式で表わすこ とができる。
C P 016. P 017. P 018< P 019)
= ^ k β * α 001 + P 003. k 7 · α 001 + p 004.
k β · Q οοι + Ρ οο5. k 5 · α 001 + Ρ οοβ)
= ( k 8 * d 0OJ + k 9 · d 000. k 7 · d 00 I + k 8 · d 000.
k 6 · d 001 + k 7 · d 000. k 5 - d ooi + k 6 - d 000) ·'· (27) また、 ROMl 4の出力データ B 3は次式で表わすことができる。
B 3= (k 4 * d 001. k s * α 001. k 2 · d 001. k 1 · d 001 1
… 28) さらに、 データ （Ρ θ20. P 021. 022. P 023) は次式で表わすこと力 できる。
( 020. P 021. P 022. P 023)
= (k 4 · d 001 + P 007. k 3 ' d 001 + P 008.
k 2 * d 001 + P 009. k 1 · d 001 + P 010)
= (ki ' dooi + ki ' d 000. ks · dooi + k4 · d0oo.
k 2 · d 001 + k 3 · d 000. k j · d 001 + k 2 · d 000) ·■· 〔29) また、 第 9番目のクロック CLKの立ち下がりと同期するデコーダ 26 の出力信号の立ち上がりにおいて、 8ビッ ト排他的論理和演算器 18の出 力データは p 023であるため、 データ d。02は次式で表わすことができ る。.
Q 002= 1 002+ Ρ θ 23= 1 002+ kj · U ooi … ( 0 以上の動作を第 {4x 20+1} 番目のクロック CLKが入力されるま で繰り返すと、 32ビッ トラッチ 20. 21, 22に合計 12シンボルの パリティ語が生成される。 今まで入力した 20シンボルの入力データの惰 報シンボル、 すなわち情報語に、 ここで生成した 12シンボルのパリティ 捂を付加すると、 合計 32シンボルの符号語、 つまり出力シンボル列が完 成する。 従って、 遅延回路 300及び出力データ選択器 310とにより、 20シンボルの情報語に統いて、 12シンボルのパリティ語が 8ビッ 卜ず つパラレルに順次、 誤り訂正符号化された符号語 （=情報語 +パリティ語） の出力データとして出力される。
以上説明したように、 本実施形態では、
(a)情報語である 8ビッ トの入力データに応答して、 生成多項式の各係 数と入力情報シンボルのガロア体上の複数の積データをそれぞれ演算して、 各ァドレスに対して 4個の積データを 1組として記憶し、 4個の積データ を 1組として並列に （同時に） 排他的論理和演算器 15乃至 18に対して 読み出し可能に構成された積データ記憶手段である 32ビッ ト ROM 14 と、
(b) 第 1の記憶手段である 3個の 32ビッ トラッチ 20. 21, 22と、
(c) 第 2の記憶手段である 8ビッ トラツチ 27と、
(d) 排他的論理和演算手段である 8ビッ ト排他的論理和演算器 15. 1 6. 17, 18と、
(e) 第 1の選択手段である 32ビッ トバス選択器 19, 20と、
(f ) 読み出し制御手段である 4進カウンタ 13、 ラッチ 12, 29及び デコーダ 24乃至 26, 28と、
( g ) 第 2の選択手段であるシンボル遅延回路 300及び出力データ選択 器 310と
を用いることによって、 最小符号間距離 d =l 3であるリード · ソロモン 符号 RS (n, n-12, d = 13 ) を符号化できる。
以上の第 1の実施形態においては、 複数の積データを記憶した ROM 1 4から 4個の積データを 1組として並列に （同時に） 排他的論理和演算器 15乃至 18に対して読み出し可能に構成し、 4個の積データを用いて同 時に処理し、 かつ 3個の 32ビッ トラッチ 20乃至 22を選択的に順次繰 り返して使用することにより、 符号化処理の演算をしているので、 回路構 成を、 図 14の従来技術の誤り訂正符号化装置の回路構成に比較して極め て簡単にすることができるとともに、 効率的にかつ高速で演算することが でき、 実用に供することが可能な符号化速度で誤り訂正符号を符号化する ことができる。
第 1の実施形態において、 第 1の記憧手段を構成する 32ビッ トラツチ 20. 21, 22の数を 3以上の数 mを増やし、 それに伴って ROM14 の内容を変更すれば、 回路構成を変更することなく、 同様な回路でさらに 最小符号間距離 dの長い誤り訂正符号も符号化できる。
<第 2の実施形態〉
図 3は、 本発明に係る第 2の実施形態の誤り訂正符号化装置の耩成を示 すブロック図である。 図 3において、 この第 2の実施形態の誤り訂正符号 化装置は、
(a) 32ビッ トデータバス 81を有し当該装置の動作を制御する CPU (中央演算制御装置） 61と、
(b) CPU61からァドレスバス 82を介して出力されるァドレスデー タと、 メモリ制御信号とに応答して、 キューメモリ 72における複数 m個 のラッチ 72— 1. 72-2, ···. 72— mに対する制御信号を発生する ラツチ制御装髭 62と、
(c) C PU61のワークエリアとして用いられる作業用 RAM63と、
(d) 8ビッ ト排他的論理和演算器 64, 65, 66. 67と、
(e) 32ビッ トバス選択器 70と、 ( f )例えば E P ROM又は E E P R OMにてなる害き換え可能な R OM (统み出し専用メモリ） であって、 CPU61によって実行される符号化 処理のプログラム及びそれを実行するために必要なデータを予め格納する
RO 71と、
(g)複数 m個の 32ビッ トラッチ 72— 1乃至 72— mを備えて、 F I FO (First-in First-out) メモリであるシフ トレジスタを構成する第 1 の記慷手段であるキューメモリ 72と、
(h) CPU 61の制御により、 キューメモリ 72の内容を一時的にラッ チして読み出す 32ビッ トラツチ 69と、
( i ) 32ビッ トラッチ 69の一部分であつて、 32ビッ トラッチ 69に おける下位 8ビッ 卜のデータをラツチする第 2の記憶手段である 8ビッ ト ラツチ 68とを備える。
第 2の実施形態では、 第 1の実施形態のバス選択器 19， 23に代わり に、 複数 m個の 32ビッ トラツチ 72— 1乃至 72— mを備えた 32ビッ ト m段のキューメモリ Ί 2を用いている。 第 2の実施形態の動作例の説明 を簡潔にするために、 キューメモリ Ί 2を構成するラッチ段数 mを 3とし、 キューメモリ 72は 3個の 32ビッ トラッチ 73. 74. 75からなる。 図 3において m= 3のときのブ Dック図を図 4に示す。 従って、 図 4を参 照して当該動作例について説明する。
図 4において、 CPU61は 32ビッ トデータバス 81に接続され、 作 窠用1¾八1^63も32ビッ トデータバス 81に接続される。 入力されて処 理対象とされる情報語のデータは、 32ビッ 卜データバス 81を介して作 業用 RAM63内の符号語バッファ Βιι ί B □ の情報語領域に書き込ま れ、 当該領域から 32ビッ トデータべス 81を介して読み出されて 8ビッ ト排他的論理和演算器 64, 65， 66. 67の第 1の入力端子に入力さ れて、 以下に詳述する符号化処理が実行された後、 上記情報語のデータに 続いて、 作業用 RAM63内の符号語バッファ Bu f B [] のパリティ語 領域からパリティ語を銪み出して符号化された符号語として出力する。 図 4において、 8ビッ ト排他的論理和演算器 64, 65, 66, 67か ら出力される 32ビッ 卜のキューメモリ 72内で縱続接続された 3個の 3 2ビッ トラッチ 73. 74, 75及び 32ビッ トラッチ 69を介して 32 ビッ トバス選択器 70の b接点に入力される。 32ビッ トラツチ 75から 出力される 32ビッ 卜の出力データのうち上位 24ビッ 卜のデータは、 排 他的論理和演算器 65. 66, 67の第 2の入力端子に入力され、 また、 8ビッ トラツチ 68からの出力データは排他的論理和演算器 65の第 2の 入力端子に入力される。 また、 32ビッ トラッチ 73から出力される 32 ビッ 卜の出力データは、 32ビッ 卜バス選択器 70の a接点に入力される。 32ビッ トバス選択器 70は、 ラッチ制御回路 62から出力される制御信 号に応答して、 a接点に入力される 32ビッ トのデータと、 b接点に入力 される 32ビッ 卜のデータとのうちの 1つの 32ビッ 卜のデータを選択的 に 32ビッ トデータバス 81を介して CPU 61及び作業用 RAM 63に 出力する。
図 4において、 縦挠接続された 3個の 32ビッ トラッチ 73, 74. 7 5はキューメモリ 72を構成しており、 32ビッ トラツチ 73は *き込み 用ラッチとして動作する一方、 32ビッ トラツチ 75は読み出し用ラッチ として勳作するように選択される。 当該選択は、 物理的には固定であるが、 キューメモリ 72へのデータの書き込み動作、 もしくはキューメモリ 72 からのデータの銃み出し動作によって、 各 32ビッ トラツチに格納されて いるデータが次段の 32ビッ トラツチに移動して行くので、 論理的には固 定ではなく、 順番に 32ビッ トラツチ内のデータを選択して行くことにな る。 本実施形態では、 C PU61から入出力制御信号 （以下、 IZO制御 信号という。 ） とともに、 ア ドレスバス 82を介して入出力ア ドレス （以 下、 IZOアドレスという。 ） をラッチ制御回路 62に送信することによ り、 ラッチ制御回路 62は、 以下に示す制御信号をラッチ 73, 74, 7 5, 69及びバス選択器 70に送信して制御する。
(a) CPU 61がァドレスデータバス 82を介して Iノ 0ア ドレスとし て "Ad r sQu eu e" をラツチ制御回路 62に出力するとともに、 I 0制御信号として "書き込み信号" をラッチ制御回路 62に出力する。 これに応答して、 ラッチ制御回路 62は、 クロック CLKに同期する書き 込みクロック信号を発生して 32ビッ トラッチ 73, 74, 75, 69に 出力する。
(b) CPU 61がァドレスデータバス 82を介して I 0ア ドレスとし て "Ad r sQu eu e" をラツチ制御回路 62に出力するとともに、 I ノ 0制御信号として "読み出し信号" をラッチ制御回路 62に出力する。 これに応答して、 ラッチ制御回路 62は、 クロック CLKに同期する眘き 込みクロック信号を発生して 32ビッ トラッチ 73. 74, 75. 69に 出力する。
(c) CPU 61がァドレスデータバス 82を介して I /0アドレスとし て "Adr s F e e d" をラッチ制御回路 62に出力するとともに、 Iノ 0制御信号として "書き込み信号" をラッチ制御回路 62に出力する。 こ れに応答して、 ラッチ制御回路 62は、 クロック CLKに同期する害き込 みク oック信号を発生して 32ビッ トラッチ 73. 74. 75に出力する c
Cd) CPU61がァ ドレスデータバス 82を介して I ZOア ドレスとし て " Ad r sC l e a rPo r t" をラツチ制御回路 62に出力するとと もに、 I/O制御信号として "省き込み信号" をラッチ制御回路 62に出 力する。 これに応答して、 ラッチ制御回路 62はクリア信号を 32ビッ ト ラッチ 69に出力して、 32ビッ トラツチ 69に記憶されているデータを 0にクリァする。
(e) CPU 61がァドレスデータバス 82を介して 1 〇ア ドレスとし て "Ad r s Qu e u e" をラツチ制御回路 62に出力するとともに、 I ノ0制御信号として "アクセス信号" をラッチ制御回路 62に出力する。 これに応答して、 ラッチ制御回路 62は、 バス選択器 70を a接点に切り 換える。 これにより、 32ビッ トラッチ 73から出力されるデータは、 バ ス選択器 70の a接点及び 32ビッ トデータバス 81を介して C PU 61 及び作業用 R AM63に入力される。
(f ) CPU 61がァドレスデータバス 82を介して Iノ 0ア ドレスとし て "Ad r sQu eu eLa s t" をラッチ制御回路 62に出力するとと もに、 I/O制御信号として "アクセス信号" をラッチ制御回路 62に出 力する。 これに応答して、 ラッチ制御回路 62は、 バス選択器 70を b接 点に切り換える。 これにより、 32ビッ トラッチ 69から出力されるデー タは、 バス選択器 70の b接点及び 32ビッ トデータバス 81を介して C PU61及び作業用 RAM 63に入力される。
図 5は、 図 3の誤り訂正符号化装置の CPU 61によって実行される符 号化処理を示すフローチャートであり、 図 6は、 図 5のサブルーチンであ る初期化処理 （ステップ S 1) を示すフローチヤ一トであり、 図 7は、 図 5のサブルーチンである符号語生成処理 （ステップ S 2) を示すフローチヤ 一トである。 また、 図 8は、 図 7のサブルーチン処理 P 1 (ステップ S 7) を示すフローチャートであり、 図 9は、 図 7及び図 8のサブルーチン処理 P2 (ステップ S 23. S 35) を示すフローチヤ一トであり、 図 10は、 図 8のサブルーチン処理 P 3 (ステップ S37) を示すフローチャー トで あり、 図 11は、 図 7のサブルーチン処理 P 4 (ステップ S 24) を示す フローチャートである。 図 5乃至図 11に図示された符号化処理の制御フ ローのプログラムは、 図 3及び図 4に示す誤り訂正符号化装置を動作させ るために、 C PU61に接統された ROM61に予め K慷され、 CPU6 1によって実行される。
図 5に示すように、 まず、 ステップ S 1で図 6に示す初期化処理を実行 した後、 ステップ S 2で図 7に示す符号語生成処理を実行して、 当該符号 化処理を終了する。
次いで、 図 6乃至図 11における処理で用いる種々の記号について説明 する。 テーブル名の [] 及びバッファ名の [] はそれぞれ配列を表し、 メ モリ領域の名前を n am eとすると、一次元配列の要素は n am e [m] 、 二次元配列の要素は n ame [m] [n] のように表し、 ここで、 m及び nはそれぞれ 0以上の整数である。 また、 配列の大きざを表すときに n a me CM] [N] と害く とすると、 有効な要素は n a m e [0] CO] か ら n ame [M— 1] [N— 1] である。
I ORe a dW (add r e s s) は、 32ビッ トのヮ一ドデータを a d d r e s sで表される I ZOァドレスから読み出したデータ値を表す関 数である。 また、 I OWr i t eW (add r e s s, da t a) は d a t aで表される 32ビッ トのヮ一ドデータを a d d r e s sで表される I Oァ ドレスに省き込む処理である。 Ge tBy t e (da t a, i nd e x).は d a t aで表される 32ビッ トのヮ一ドデータの上位から i nd e X番目のバイ トデータを表す関数である。 ただし、 i n d e xは 1から數 える自然数である。
スラッシュ記号 ソ" は整数の除算を表わす二項演算子であり、 A M OD Bは Aを Bで除箕したときの剰余を演算する二項演算子である。 ま た、 ANDはビッ トごとの論理積を演算する二項演算子であり、 EORは ビッ トごとの排他的論理和を演算する二項演算子である。
さらに、 配列名を n ameとすると、 name [x. ···, y] は配列 n am eの x番目の要素から y番目の要素までを表す。 変数名又は配列名の 最後の 1文字である W. Bは、 それぞれ 32ビッ 卜のデータ、 8ビッ 卜の データを表す。
ガロア体演算テーブル tGa l o i sW [nQu e u e La t ch] [2 56] は、 入力データと生成多項式の各係数とのガロア体上の積のデータ であって、 予め演算されて ROM71に格納された後、 C PU61の初期 化時や、 誤り訂正符号の最小符号間距離 dの変更に伴う初期化処理におい て、 ROM71から作業用 RAM63内の領域に転送されて書き込まれる。 第 1の実施形態と同様の 12シンボルのパリティ語を付加する場合では、 表 1及び表 2に示した ROM 14の内容と同一のデータが当該ガロア体演 算テーブル t Ga l o i sW [nQu eu eLa t ch] [256] に予 め記慷される （ステップ S 11) 。 ただし、 t G a 10 i sW [m] [n] は、 第 1の実施形態における ROM14のァドレス Hを mとし、 ァドレス Lを nとしたデータ内容を表す。
符号語バッファ Bu i B [] は、 作業用 RAM63内の領域に設定され たバッファメモリであり、 情報語領域とパリティ語領域とに分割され、 当 該符号語バッファ Bu i B [] の情報語領域において、 この符号化処理を 実行する前に入力された符号化すべき情報語が先頭から予め格納される一 方、 符号語バッファ Bu i B [] のパリティ語領域において、 上記入力さ れた情報語に基づいて当該符号化処理を実行したときに得られるパリティ 語が格納された後、 情報語とパリティ語が符号語として外部装置に出力さ れる。 I ZOァドレスの A d r s Qu e u e La s tは、 32ビッ トラッチ 7 3の内容を読み出すためのアドレスである。 ここで、 CPU61が 1ノ0 制御信号の "読み出し信号" とともに、 1ノ0ア ドレスとして "Ad r s Qu e u e L a s t " をラツチ制御回路 62に出力した場合であっても、 上述のように、 32ビッ トラッチ 73. 74, 75. 69に対して書き込 みクロック信号を発生しないので、 キューメモリ 72内の記億データの内 容はそのままである。
表 4は、 図 5乃至図 11のフローチャートに従って本実施形態の誤り訂 正符号化装 Sが動作する埸合において、 本動作例での図 4の各 32ビッ ト ラッチ 73, 74. 75, 69の記憶データを示す。 表 4における二重下 線はデータの香き込みを表し、 下線はデータの読み込みを表す。 また、 p 000から始まるパリティシンボルの記号は、 第 1の実施形態のものと同一 であり、 図 13に示す従来技術の計算方法で演算される値である。
(以下余白）
一 6ε一
Figure imgf000041_0001
998Z0/96df/lDd 以下に、 第 1の実施形態と同様に、 本実施形態を用いて 8ビッ トを 1シ ンボルとしたリード ' ソロモン符号 RS (32, 20, d = 13) を符号 化する処理例 （以下、 第 1の動作例という。 ） を、 図 6乃至図 11及び表 4を参照して説明する。 本動作例の場合、 情報シンボル数 n I n f 0は 2 0であり、 パリティシンボル数 nP a r i t yは 12である。
まず、 図 6の初期化処理について以下説明する。
図 6のステップ S 11において、 ガロア体演算テーブル t G a 】 0 i s [nQu e u e L a t c h] [256] の初期化を行う。 本動作例の場合、 キューメモリ 72を構成する 32ビッ トラツチの数 nQu e u e L a t c h ( = m) は 3である。 本動作例のように最小符号間距離 dが 13の場合、 ガロア体演算テーブル t G a 1 0 i s [nQu e u e L a t c h] [25 6] の内容は、 表 1と表 2に示す第 1の実施形態における ROM14のデ ータ内容と同一になるように ROM71から作業用 RAM63に転送され て初期化される。 また、 32ビッ トラッチ 73, 74, 75, 69は 0に クリアされる。 この処理は表 4のステップ S 1001に対応する。
次いで、 ステップ S 12において、
nFeed = nQueueLatch- (nParity- 3 ) Z 4 … （31) で表すことができるキューメモリ 72のフィード回数 nF e e dを演算し て、 フィード回数パラメータ nF e e dに代入される。 本動作例の場合、 キューメモリ 72を構成する 32ビッ トラツチの数 nQu e u e L a t c h 3であり、 付加するパリティ シンボル数 n P a r i t yは 12である から、 キューメモリ 72のフィード回数 nF e e dは 0に初期化される。 次いで、 ステップ S 13において、
nQ= (nParity+3) / - (32) で表すことができるキューメモリ Ί 2の害き込み数 nQを演算して書き込 み数パラメータ nQに代入される。 本動作例の場合、 付加するパリティシ ンボル数 n Pa r i t yは 12であるから、 キューメモリ 72の書き込み 数 n Qは 3になる。
次いで、 ステップ S 14において、
index= ( (nParity-l- 3 ) MOD 4) + 1 ." (33) で表すことができるキュー溢れシンボル取り出し位置 i n d e xを演算し て、 キュー溢れシンボル取り出し位置パラメータ i n d e xに代入する。 ここで、 キュー溢れシンボル取り出し位置 i nd exは、 キューメモリ 7 2を 8ビッ ト X n P a r i t y段のキューとして動作させるために、 擬似 的にキューメモリ 72の nP a r i t y段目から 8ビッ トシンボルが溢れ たように取り出す位置を示す。 本動作例の場合、 付加するパリティシンポ ル数 nP a r i t yは 12であるから、 キュー溢れシンボル取り出し位 S i n d e xは 4になる。 以上で初期化処理を終了する。
次に、 図 7から図 11を参照して実際の符号語生成処理を説明する。 まず、 図 7のステップ S21において、 作業用 RAM63内の符号語バッ ファ Bu f B [] から情報語を銃み出し、 当該符号語生成処理によって生 成したパリティ語をキューメモリ 72上に作成する。 この処理をサブルー チン処理 P 1とする。
次に、 サブルーチン処理 P 1の内容を図 8を参照して具体的に説明する。 まず、 図 8のステッブ S 31において、 情報シンボルカウンタ c n tを 0 に初期化し、 ステップ S 32において、 符号語バッファから情報シンボル カウンタ c n t番目の 8ビッ 卜の情報シンボル B u f B [c n t ] を読み 出して入力データ i nD a t a Bとする。 この場合、 情報シンボルカウン タ c n tは 0であるから、 入力データ i nD a t a Bは、 符号語バッファ の先頭のシンボルである。 以後、 ここで取り出した先頭の情報シンボルを i 000とする。 次いで、 ステッブ S 33において、 入力ポートである 32 ビッ トラッチ 73から 32ビッ 卜のデータを読み出し、 その上位から i n d e x (本動作例の場合は 4) バイ 卜目、 つまり下位 8ビッ トを得る。 こ の場合、 32ビッ トラッチ 73の内容は、 クリアされて 00000000 Hであるので、 その下位 8ビッ トは 00Hである。 これは表 4のステップ S 1002に対応する。 さらに、 ステップ S 34において、 出力ポー卜で ある 32ビッ トラッチ 69の内容を 0にクリァする。 これは表 4のステツ ブ S 1003に対応する。
次いで、 ステップ S 35において、 キューメモリ 72の内容を、 キュー メモリ 72のフィード回数 nF e e d回だけ進める。 当該処理においては、 32ビッ トラツチ 75のデータを 32ビッ トラツチ 69に書き込み、 32 ビッ トラツチ 74のデータを 32ビッ トラツチ 75に書き込み、 32ビッ トラツチ 73のデータを 32ビッ トラッチ 74に書き込む。 ここで、 フィ 一ド回数 n Fe e d回だけ進めるとは、 上記ラツチからラツチへの害き込 み処理を n F e e d回だけ繰り返すことを意味する。 ここで、 入力ポート である 32ビッ トラツチ 73のデータはそのまま保存される。 この処理を サブルーチン処理 P 2とする。
次に、 サブルーチン処理 P 2の内容を図 9を参照して具体的に説明する。 まず、 図 9のステップ S 41において、 キューメモリ 72のフィードカウ ン夕の計数値 cn tFe e dをキュー 72のフィード回数 nF e e dに初 期化する。 本動作例の場合、 フィード回数 nF e e dは 0であるので、 計 数値 c n t F e e dは 0になる。 次いで、 ステップ S 42において、 キュ 一メモリ 72のフィードカウンタの計数値 c n t F e e dは 0であるから、 サブルーチン処理 P 2を終了して図 8の元のサブルーチン処理 P 1に戻る。 つまり、 本動作例の場合、 サブルーチン処理 P 2では何も実行しない。 図 8のステップ S 36において、 入力データ i nD a t a Bとステップ S 33で求めた 32ビッ トラツチ 73の下位 8ビッ トのデータ p D a t a Bとの排他的論理和を求め、 演算結果のデータ d a t a Bの値を d。00と する。 この場合、 入力データ i oとデータ 00Hとの排他的論理和なの で、 第 1の実施形態と同様に、 演算結果のデータ dDDcは式 （15) で表 される。 次いで、 ステップ S 3 7において、 ステップ S 3 6で求めた演算 結果のデータ d a t a Bと生成多項式の各係数との積を作業用 RAM63 内のガロア体演算テーブルから読み出してキューメモリ 7 2に香き込む。 この処理をサブルーチン処理 P 3とする。
次に、 サブルーチン処理 P 3の内容を図 10を参照して具体的に説明す る。 まず、 図 10のステップ S51において、 キュー害き込みカウンタの 計数値 c n tWQを 0に初期化する。 次いで、 ステップ S 52において、 ステップ S 36で求めたデータ d。。。と生成多項式 （式 （14) ) の係数 とのガロア体上の積を、 4シンボル （32ビッ ト） だけ作業用 RAM63 内のガロア体演算テーブルから読み出す。 ここで、 キュー書き込みカウン 夕の計数値 c n tWQが 0の時には、 生成多項式 （式 （14) ) の係数と して k12, ku, kio, k9が選ばれる。 次いで、 ステップ S 5 3におい て、 ステップ S 52で読み出したガロア体上の積のデータをキューメモリ 72に害き込む。 このとき、 32ビッ トラッチ 75は、 データ 00000 000Hを出力しており、 8ビッ トラッチ 68はデータ 00Hを出力して いるので、 排他的論理和演算器 64, 65, 66, 67の入力データはデ 一夕 （00H, 00H. 00H, 00H) と、 データ （k12 · d 000. i · d ooo. kio - dooo. k9 · dooo) である。 従って、 排他的論理和演 算器 64. 65， 66. 67の出力データを （p 000. p00i, p 002, p。
03) すると、 第 1の実施形態と同様に、 このデータ値は式 （19) で表す ことができる。 これは表 4のステップ S 1004に対応する。
次いで、 ステップ S 54において、 キュー書き込みカウンタの計数値 c n tWQを 1だけインクリメントする。 このとき、 キュー書き込みカウン タの計数値 c n t WQは 1になる。 そして、 ステップ S 55において、 キュ 一書き込みカウンタの計数値 c n tWQがキュー害き込み数 nQより小さ い場合は、 ステップ S 52に戻る一方、 そうでない場合はサブルーチン処 理 P 3を終了してリターンする。 この場合、 キュー書き込みカウンタの計 数値 cn tWQは 1であり、 キュー書き込み数 nQは 3であるから、 ステツ ブ S 52に戻る。
次いで、 ステップ S 52において、 ステップ S 36で求めたデータ d00 0と生成多項式 （式 （14) ) の係数とのガロア体上の積を、 4シンボル (32ビッ ト） 求める。 その際に、 ガロア体演算テーブルを用いるが、 キュ 一書き込みカウンタの計数値 c n tWQが 1の時には、 生成多項式 （式 （1 4) ) の係数として ke， k7. k6. k5が選ばれる。 さらに、 ステップ S
52において、 ステップ S 52で求めた積のデータをキューメモリ 72に 害き込む。 このとき、 32ビッ トラッチ 75はデータ OOOO00O0H を出力しており、 8ビッ トラツチ 68はデータ 00 Hを出力しているので、 排他的論理和演算器 64, 65. 66, 67の入力データは、 （0OH.
00H, 00H, 00H) と、 データ （k8 · d 000, k7 · d。00. k6 · d ooo. k 5 · d 0。0) である。 従って、 排他的論理和演算器 64. 65.
66.. 67の出力を （P 0< , P OOS. P 006. P。D7) とすると、 第 1の実 施形態と同様に、 このデータ値は式 （21) で表すことができる。 これは 表 4のステップ S1005に対応する。
次いで、 ステップ S54において、 キュー書き込みカウンタの計数値 c n t WQを 1だけインクリメントする。 このとき、 キュー害き込みカウン タの計数値 c n t WQは 2になる。 さらに、 ステップ S 5 5において、 キュ 一香き込みカウンタの計数値 c n t WQがキュー *き込み数 n Qより小さ い場合は、 ステップ S 5 2に戻る一方、 そうでない場合はサブルーチン処 理 P 3を終了してリターンする。 この場合、 キュー書き込みカウンタの計 数値 c n t WQは 2であり、 キュー書き込み数 n Qは 3であるから、 ステツ ブ S 5 2に戻るカ^ その後、 上記の処理と同様にステップ S 5 2、 ステツ ブ S 5 3、 ステップ S 5 4を経て、 再びステップ S 5 5に進む。 この時、 キュー書き込みカウンタの計数値 c n t WQは 3であるから、 当該サブル 一チン処理 P 3を終了して、 図 8のサブルーチン処理 P 1に戻る。
図 8のステップ S 3 8において、 情報シンボルカウンタの計数値 c n t を 1だけインクリメン卜する。 このとき、 情報シンボルカウンタの計数値 c n tは 1になる。 そして、 ステップ S 3 9において、 情報シンボルカウ ンタの計数値 c n tが情報シンボル数 n I n f oより小さい場合はステツ ブ S 3 2に戻る一方、 そうでない場合はサブルーチン処理 P 1を終了して リターンする。 この場合、 情報シンボルカウンタの計数値 c n tは 1であ り、 かつ情報シンボル数 n I n f oは 2 0であるから、 ステップ S 3 2に
B ^る。
ステップ S 3 2において、 符号語バッファから情報シンボルカウンタの 計数値 c n t番目の情報シンボル B u f B [ c n t ] を読み出す。 この場 合、 情報シンボルカウンタの計数値 c n tは 1であるから、 符号語バッファ の先頭から 2番目のシンボルである。 ここで読み出した 2番目の情報シン ボルを i。 とする。 次いで、 ステップ S 3 3において、 3 2ビッ トラッ チ 7 3から 3 2ビッ 卜のデータを読み出し、 その上位から i n d e x (本 動作例の場合は 4 ) バイ ト目、 つまり下位 8ビッ 卜のデータを得る。 この 場合、 3 2ビッ トラッチ 7 3内のデータはデータ （P。。8 . P c o s . P 0 1 0 . P OM) であるので、 その下位 8ビッ トのデータは pDUである。 これは表 4のステップ S 1007に対応する。 さらに、 ステップ S34において、 32ビッ トラプチ 69の内容をクリアする。 これは表 4のステップ S 10 08に対応する。
次いで、 ステップ S35において、 キューメモリ 72の内容を、 キュー メモリ 72のフィード回数 n F e e d回だけ進めるが、 上記の処理と同様 に、 本動作例の場合、 当該サブルーチン処理 P 2において何も実行しない。 さらに、 ステップ S 36において、 入力データ i nDa t aBとステップ S 33で求めた 32ビッ トラツチ 73の下位 8ビッ 卜のデータとの排他的 論理和を演算し、 演算結果のデータ値を dD01とすると、 この場合、 入力 データ i。 とデータ p。,！との排他的論理和なので、 第 1の実施形態と同 様に、 演算結果のデータ dD(Jlは式 （16) で表される。 さらに、 ステツ プ S 37において、 ステップ S 36で求めたデータ値と生成多項式の各係 数との積を、 キューメモリ 72に害き込む処理であるサブルーチン処理 P 3を実行する。
次に、 サブルーチン処理 P 3の内容を図 10を参照して具体的に説明す る。 まず、 図 10のステップ S 51において、 キュー害き込み力ゥンタの 計数値 c n tWQを 0に初期化し、 ステップ S52において、 ステップ S 36で求めたデータ d。clと生成多項式 （式 （14) ) の係数とのガロア 体上の積を、 4シンボル （32ビッ ト） 求める。 その際に、 ガロア体演算 テーブルを用いるが、 キュー害き込みカウンタの計数値 c n tWQが 0の 時には、 生成多項式 （式 （14) ) の係数として k12. k,,. k10. ke が選ばれる。 そして、 ステップ S 53において、 ステップ S 52で求めた 結果のデータをキューメモリ 72に害き込む。 このとき、 32ビッ トラッ チ 75はデータ （P ooo. P 001. P 002, P oos) を出力しており、 8ビッ 卜ラッチ 68はデータ 00Hを出力しているので、 排他的論理和演箕器 6 4, 65. 66. 67の入力データはデータ （00H, ρ 000. Ροοι. oo 2ノ と 7 "*一 ^ (k.12 · d oDi- k 11 · d ooi. k】o * aoo，. kg * d 001 ) である。 従って、 排他的論理和演算器 64, 65, 66, 67の出力デー タをデータ （P oi2, P 013. P OM, P 015) とすると、 第 1の実施形態と 同様に、 このデータ値は式 （25) で表すことができる。 これは表 4のス テツブ S 1009に対応する。
次いで、 ステップ S 54において、 キュー書き込みカウンタの計数値 c n t WQを 1だけインク リ メ ン トする。 このとき、 キュー書き込みカウン タの計数値 c n tWQは 1になる。 さらに、 ステップ S 55において、 キュ ー窨き込みカウンタの計数値 c n tWQがキュー書き込み数 nQより小さ い場合はステップ S 52に戻る一方、 そうでない場合は当該サブルーチン 処理 P 3を終了してリターンする。 この場合、 キュー謇き込みカウンタの 計数値 c n tWQは 1であり、 キュー窨き込み数 n.Qは 3であるから、 ス テツブ S 52に戻る。
ステップ S 52において、 ステップ S 36で求めたデータ domと生成 多項式 （式 （14) ) の係数とのガロア体上の積を、 4シンボル （32ビッ ト） 求める。 その際に、 ガロア体演算テーブルを用いるが、 キュー書き込 みカウンタの計数値 c n tWQが 1の時には、 生成多項式 （式 （14) ) の係数として ke, k7, ke, k5が選ばれる。 そして、 ステップ S 53に おし、て、 ステップ S 52で求めた結果データをキューメモリ Ί 2に書き込 む。 このとき、 32ビッ トラツチ 75はデータ （Ρ θΙΜ. P 005. P 006.
Ροοτ) を出力しており、 8ビッ トラツチ 68はデータ ρ。。3を出力してい るので、 排他的論理和演算器 64, 65, 66, 67の入力データはデー タ (P。Q3. P 004. P O0S. P 006； とァ—タ 8 * 0。。1, k 7 * Q 001. k6 - dooi. k5 · do(n) である。 従って、 排他的論理和演算器 64, 6 5, 66, 67の出力データをデータ （p01 6. P 01 7. P 018. P 01 9ノ と すると、 第 1の実施形態と同様に、 このデータ値は式 （27) で表すこと ができる。 これは表 4のステップ S 1010に対応する。
次いで、 ステップ S54において、 キュー書き込みカウンタの計数値 c n tWQを 1だけインクリメントする。 このとき、 キュー香き込みカウン タの計数値 c n tWQは 2になる。 次いで、 ステップ S 55において、 キュ 一書き込みカウンタの計数値 c n t WQがキュー害き込み数 nQより小さ い埸合はステップ S 52に戻る一方、 そうでない場合はサブルーチン処理 P3を終了してリターンする。 この場合、 キュー害き込みカウンタの計数 値 cn tWQは 2であり、 キュー書き込み数 nQは 3であるから、 ステツ ブ S 52に戻る。 その後、 上記の処理と同様にステップ S 52、 ステップ S 53、 ステップ S 54を経て、 再びステップ S δ 5に進む。 この時、 キュ ー窨き込みカウンタの計数値 c n tWQは 3であるから、 当該サブルーチ ン処理 P 3を終了して、 図 8のサブルーチン処理 P 1にリターンする。 図 8のステップ S 38において、 情報シンボルカウンタの計数値 c n t を 1だけインク リメ ントする。 このとき、 情報シンボルカウンタの計数値 c η ΐは 2になる。 次いで、 ステップ S 39において、 情報シンボルカウ ンタの計数値 c n tが情報シンボル数 n I n f oより小さい場合はステツ ブ S 32に戻り、 そうでない場合はサブルーチン処理 P 1を終了してリタ ーンする。 この場合、 情報シンボルカウンタの計数値 c n tは 2であり、 情報シンボル数 n I n f 0は 20であるから、 ステップ S 32に戻る。 ステップ S 32において、 符号語バッファから情報シンボルカウンタの 計数値 c n t番目の情報シンボル B u ί B [c n t] を読み出す。 この場 合、 惰報シンボルカウンタの計数値 c n tは 2であるから、 符号語バッファ の先頭から 3番目のシンボルである。 ここで取り出した 3番目の情報シン ボルをデータ i awとする。 そして、 ステップ S 33において、 32ビッ トラツチ 73から 32ビッ トのデータを読み出し、 その上位から i n d e x (本勳作例の場合は 4) バイ ト目、 つまり下位 8ビッ トを得る。 この場 合、 32ビッ トラッチ 73の内容はデータ （P 02D, P 021. P 022. P 023> であるので、 その下位 8ビッ トのデータは p。23である。 これは表 4のス テツブ S 1012に対応する。 次いで、 ステップ S 34において、 出力ポ ートの 32ビッ トラッチ 69の内容をクリアする。 これは表 4のステップ S 1013に対応する。 そして、 ステップ S 35において、 キューメモリ 72の内容を、 キューメモリ 72のフィード回数！！ F e e d回だけ進める が、 上記の処理と同様に、 本動作例の場合、 当該サブルーチン処理 P 2に おいて何も実行しない。
次いで、 ステップ S 36において、 入力データとステップ S 33で求め た 32ビッ トラツチ 73の下位 8ビッ トのデータとの排他的論理和を求め る。 このデータ値を d。02とすると、 この場合、 入力データ i DMとデータ p 023との排他的論理和なので、 第 1の実施形態と同様に、 データ d 002は 式 （30) で表される。 以下、 上記の処理と同様に、 ステップ S 37、 S 38、 S 39と進み、 さらに、 情報シンボルカウンタの計数値 c n tが情 報シンボル數 n I n f o (本動作例の場合は 20) に一致するまで、 ステツ ブ S 32からステップ S 39までの処理を繰り返し、 サブルーチン処理 P 1を終了して図 7のメィンルーチンに戻る。
そして、 図 7のステップ S 22において、 キューメモリ 72から溢れた 32ビッ トのデータをダミ一データとして読み出す。 これは表 4のステッ ブ S 1102に対応する。 次いで、 ステップ S 23において、 キューメモ リ Ί 2の内容を、 キューメモリ 72のフィー ド回数 n F e e d回だけ進め るが、 上記の処理と同様に、 本動作例の場合、 当該サブルーチン処理 P 2 において何も実行しない。 次いで、 ステップ S 24において、 キューメモ リ 72からパリティシンボルを 4シンボルずつ合計 n P a r i t yシンポ ル统み出し、 符号語バッファ Bu f B [] のパリティ語領域に格納する。 この処理をサブルーチン処理 P 4とする。
次に、 サブルーチン処理 P 4の内容を図 11を参照して具体的に説明す る。 まず、 ステップ S 61において、 キュー読み出しカウンタの計数値 c n t RQを 0に初期化する。 次いで、 ステップ S 62において、 キューメ モリ 72からパリティシンボルを 4シンボルずつ読み出し、 ステップ S 6 3において、 苻号語バッファのパリティ語領域に、 ステップ S 62で取り 出した 4シンボル （32ビッ ト） 分のパリティシンボルを格納する。 この 場台、 情報シンボル数 n I η ί 0は 20であり、 キュー読み出しカウンタ の計数値 c n t RQは 0であるから、 符号語バッファに格納する位置 B u f B [n I n f o + c n tRQ - 4. ··.. n I n f o + cn tRQ - 4 + 3] は B u ί B [20, ···. 23] となる。 本実施形態の場合、 4シンポ ル （=32ビッ ト） 分のデータ （a. b, c, d) を符号語バッファ Bu f B [ i . ···, i + 3] に格納する場合、 Bu f B [ i 3 にはデータ aが、 Bu f B [ i十 1] にはデータ bが、 Bu f B [i + 2] にはデータじが、 Bu i B [i + 3] にはデータ dが格納されるものとする。
さらに、 ステップ S64において、 キュー読み出しカウンタの計数値 c n t RQを 1だけィンクリメン卜する。 この場合、 計数値 c n t RQは 1 になる。 次いで、 ステップ S 65において、 キュー読み出しカウンタの計 数値 c n t RQがキュー書き込み回数 nQより小さい場合、 ステップ S 6 2に戻る一方、 そうでない場合、 当該サブルーチン処理 P 4を終了してリ ターンする。 この場合、 計数値 c n t RQは 1であり、 キュー書き込み回 数 nQは 3であるから、 ステップ S 62に戻る。
次に、 ステップ S 62において、 キューメモリ 72からパリティシンポ ルを 4シンボルずつ銃み出し、 ステップ S 63において、 苻号語バッファ のパリティ語領域に、 ステップ S 62で読み出した 4シンボル （=32ビッ ト） 分のパリティシンボルを格納する。 この場合、 情報シンボル数 n I n f oは 20であり、 キュー読み出しカウンタの計数値 c n t RQは 1であ るから、 符号語バッファに格納する位置 B u f B [n I n f 0 + c n t R Q · 4, ···, n I n f o+ c n t RQ - 4 + 3] は Bu f B [24. ···. 27] となる。 そして、 ステップ S 64において、 キュー読み出しカウン タの計数値 c n t RQを 1だけィンクリメン卜する。 この場合、 計数値 c n t RQは 2になる。 さらに、 ステップ S 65において、 キュー読み出し カウンタの計数値 c n t RQがキュー害き込み数 nQより小さい場合、 ス テツブ S 62に戻る一方、 そうでない場合、 当該サブルーチン処理 P 4を 終了してリターンする。 この場合、 計数値 c n t RQは 2であり、 書き込 み回数 n Qは 3であるから、 ステップ S 62に戻る。 以降、 ステップ S 6 2、 S 63、 S 64の処理を同様に実行し、 その後ステップ S 65に進む。 このとき、 計数値 c n t RQは 3であり、 香き込み回数 nQは 3であるか ら、 当該サブルーチン処理 P 4を終了して元のメインルーチンに戻る。 上 記サブルーチン処理 P 4は、 表 4のステップ S 1103、 S 1104、 及 び S 1105の処理に対応する。
以上で、 本動作例である RS (32, 20, d = 13) の符号語生成処 理を終了する。 ただし、 符号語は符号語バッファ Bu ί B [0, -. n I n f o + nP a r i t y-1] に格納されている。 この場合、 情報シンポ ル数 n I n f 0は 20、 パリティシンボル数 n P a r i t yは 12である から、 符号語は符号語バッファ Bu f B [0, ···, 31] に格納されてい る。
次に、 本実施形態の誤り訂正符号化装置を用いて、 上記第 1の動作例と 異なる最小符号間距離 dを有し、 8ビッ トを 1シンボルとしたリード . ソ ロモン符号 RS (15. 10. d = 6) を符号化する処理について、 図 5 乃至図 11及び表 5を用いて説明する。 これを第 2の動作例とする。 ただし、 原始多項式 m (X) と原始元なは、 第 1の実施形態と同様にそ れぞれ式 （12) 、 式 （13) で表される。 ただし、 生成多項式 G (X) は次式で表わすことができる。
G (X)
8
= Π (X - α〖）
i =0
= · Xe+k2 · X7 +…十 ke · X + k9 ·'· (34) 従って、 第 2の動作例では、 係数 kn (l≤n≤5) の値が第 1の実施 形態や本実施形態の第 1の動作例とは異なる。
表 5は、 図 5乃至図 11のフローチャートに従って、 誤り訂正符号化装 置が動作する場合において、 本動作例での図 4の各 32ビッ トラツチの状 態である。 表 5の 2重下線はデータの書き込みを表し、 下線はデータの読 み込みを表す。 また、 データ Ρ οοοから始まるパリティシンボルの記号や データ d。00から始まる記号は、 第 1の実施形態や本実施形態の第 1の動 作例における記号と異なり、 図 14に示すような計算方法で求められる値 である。 本動作例の場合、 情報シンボル数 n I n f 0は 10であり、 パリ ティ シンボル数 n P a r i t yは 5である。
Figure imgf000055_0001
9
98Z0/96dT/lDd 8 Π 6 OAV 以下に、 本実施形態の第 2の動作例における初期化処理について図 6を 参照して説明する。
まず、 図 6のステップ S 11において、 ガロア体演算テーブル t G a 1 o i s [nQu e ueLa t c h] [256] の初期化を行う。 本動作例 の場合、 キューメモリ 72を構成する 32ビッ トラツチの数 nQu e u e La t e hは 3である。 本動作例のように最小符号間距離が 6の場合、 ガ 口ァ体演算テーブルの内容は、 表 6及び表 7に示す内容となるように初期 化される。 また、 32ビッ トラッチ 73, 74, 75, 69を 0にクリア する。 これは表 5のステップ S 2001に対応する。
(以下余白）
表 6
Figure imgf000057_0001
表 7
Figure imgf000058_0001
次に、 ステップ S 12において、 式 （31)で表わされるキューメモリ 72のフィード回数 nF e e dを求める。 本動作例の場合、 キューメモリ 72を構成する 32ビッ トラツチの数 n Qu e u e L a t c hは 3であり、 付加するパリティシンボル数 nP a r i t yは 5であるから、 キューメモ リ 72のフィード回数 nF e e dは 1になる。 次いで、 テツブ S 13にお いて、 式 （32) で表わされるキューメモリ 72の書き込み数 nQを求め る。 本動作例の場合、 付加するパリティシンボル数 n Pa r i t yは 5で あるから、 キューメモリ 72の香き込み数 nQは 2になる。 さらに、 ステツ ブ S 14において、 式 （33) で表わすことができるキュー溢れシンボル 取り出し位置 i n d e xを求める。 本動作例の場合、 付加するパリティシ ンボル数 n P a r i t yは 5であるから、 キュー溢れシンボル取り出し位 置 i 1 (16乂は1になる。 以上で初期化処理を終了する。
次に、 図 7乃至図 11を用いて実際の符号語生成処理を説明する。 まず、 図 7のステップ S 21において、 作業用 RAM 63内の符号語バッファ B u f B [] から情報語を読み出し、 パリティ語をキューメモリ 72上に作 成するサブルーチン処理 P 1を実行する。 ここで、 以下、 当該サブルーチ ン処理 P 1の内容を図 8を参照して具体的に説明する。
まず、 図 8のステップ S 31において、 情報シンボルカウンタの計数値 c n tを 0に初期化する。 次いで、 ステップ S 32において、 符号語バッ ファから情報シンボルカウンタの計数値 c n t番目の情報シンボル B u f B [c n t] を読み出す。 この場合、 情報シンボルカウンタの計数値 c n tは 0であるから、 符号語バッファの先頭のシンボルである。 以後、 ここ で読み出した先頭の情報シンボルをデータ i。0oとする。 さらに、 ステツ ブ S 33において、 32ビッ トラッチ 73から 32ビツ 卜のデータを読み 出し、 その上位から i ndex (本動作例の場合は 1) バイ ト目、 つまり 上位 8ビッ トを得る。 この場合、 32ビッ トラツチ 73の内容は、 クリア されて 00000000Hであるので、 その上位 8ビッ 卜のデータはデー タ 00Hである。 これは表 5のステップ S 2002に対応する。 次いで、 ステップ S 34において、 32ビッ トラツチ 69の内容を 0にクリアする。 これは表 5のステップ S 2003に対応する。 さらに、 ステップ S35に おいて、 キューメモリ 72の内容を、 キューメモリ 72のフィード回数 n Fe e d回だけ進めるサブルーチン処理 P2を実行する。
次に、 このサブルーチン処理 P 2を図 9を参照して具体的に説明する。 まず、 ステップ S 41において、 キューメモリ 72のフィードカウンタの 計数値 c n t F e edをキューメモリ 72のフィード回数 nF e e dに初 期化する。 本動作例の場合、 フィード回数 n F e e dは 1であるので、 計 数値 c n t F e e dは 1になる。 次いで、 ステップ S 4 2において、 キュ 一メモリ 7 2のフィードカウンタの計数値 c n t F e e dが 0より大きけ ればステップ S 4 3に進む一方、 そうでないならサブルーチン処理 P 2を 終了してリターンする。 この場合、 計数値 c II t F e e dは 1であるから， ステップ S 4 3に進む。 ステップ S 4 3において、 キューメモリ 7 2の内 容を進める。 ただし、 この時 3 2ビッ トラツチ 6 9の内容はそのままに保 たれる。 これは表 5のステップ S 2 0 0 4に対応する。 次いで、 ステップ S 4 4でキューメモリ 7 2のフィードカウンタの計数値 c n t F e e dを 1だけデクリメン卜する。 この場合、 計数値 c n t F e e dは 0になる。 そして、 ステップ S 4 2において、 キューメモリ 7 2のフィードカウンタ の計数値 c n t F e e dが 0より大きければステップ S 4 3に進む一方、 そうでないならサブルーチン処理 P 2を終了してリターンする。 この場合、 計数値 c n t F e e dは 0であるから、 サブルーチン処理 P 2を終了して、 図 8のサブルーチン処理 P 1に戻る。
図 8のステップ S 3 6において、 入力データとステップ S 3 3で求めた 3 2ビッ トラッチ 7 3の上位 8ビッ トのデータとの排他的論理和を求める。 このデータ値を d 000とすると、 この場合、 入力データ i oとデータ 0 0 Hとの排他的論理和なので、 データ d o o oは次式で表わすことができる。
U 0 0 0 = 1 0 0 0 "* ( 3 5 ) 次いで、 ステップ S 3 7において、 ステップ S 3 6で求めたデータ値と 生成多項式の各係数との積をキューメモリ 7 2に書き込むサブルーチン処 理 P 3を実行する。 以下、 このサブルーチン処理 P 3を図 1 0を参照して 具体的に説明する。
まず、 図 1 0のステップ S 5 1において、 キュー害き込みカウンタの計 数値 c n tWQを 0に初期化し、 ステップ S 52において、 ステップ S 5 6で求めたデータ d no。と生成多項式 （式 （34) ) の係数とのガロア体 上の積を、 4シンボル （32ビッ 卜） だけ求める。 その際に、 ガロア体演 算テーブルを用いるが、 キュー窨き込みカウンタの計数値 c n t WQが 0 の時には、 生成多項式 （式 （34) ) の係数として k 5, k 4. k 3, k 2が 選ばれる。 さらに、 ステップ S 53において、 ステップ S 52で求めた結 果のデータをキューメモリ 72に窨き込む。 このとき、 32ビッ トラッチ 75はデータ 00000000Hを出力しており、 8ビッ トラッチ 68は データ 00Hを出力しているので、 排他的論理和演算器 64, 65, 66, 67の入力データは、 データ （00H, 0 OH, 00H, 00H) と、 デ ータ （k s · d k 3 · d ooo， k 2 · d ooo) である。 従つ て、 排他的論理和演算器 64, 65, 66, 67の出力データをデータ （p 000* P DOい P 00 Z. P 003 ) とすると、 このデータは次式で表わすことが できる。
. P ooo. Pooi. P 002. oos)
= ( k 5 * d ooo. k 4 · d ooo. k s * a ooo. k 2 · a ooo) ( ύ 6 ) これは表 5のステップ S 2005に対応する。
次に、 ステップ S 54において、 キュー害き込みカウンタの計数値 c n tWQを 1だけインクリメントする。 この場合、 キュー害き込みカウンタ の計数値 c n t WQは 1になる。 次いで、 ステップ S 55において、 キュ 一書き込みカウンタの計数値 c n tWQがキュー書き込み数 nQより小さ い場合はステップ S 52に戾り、 そうでない場合はサブルーチン処理 P 3 を終了してリターンする。 この場合、 キュー香き込みカウンタの計数値 c n tWQは 1であり、 キュー書き込み数 n Qは 2であるから、 ステップ S 52に戻る。 ステップ S 52において、 ステップ S 36で求めたデータ d 00。と生成 多項式 （式 （34) ) の係数とのガロア体上の積を、 4シンボル （32ビッ ト） だけ求める。 その際に、 ガロア体演算テーブルを用いる力 キュー害 き込みカウンタの計数値 c n t WQが 1の時には、 生成多項式 （式 （14) ) の係数として k，， 0, 0. 0が選ばれる。 次いで、 ステップ S 53に おいて、 S 52で求めた結果のデータをキューメモリ 72に書き込む。 こ のとき、 32ビッ トラッチ 75はデータ 00000000Hを出力してお り、 8ビッ トラツチ 68はデータ 00Hを出力しているので、 排他的論理 和演箕器 64. 65. 66. 67の入力データは、 データ （00H. 00 H. 00H. 00H) と、 データ （k! · doco, 0 OH, 0 OH, 0 OH) である。 従って、 排他的論理和演算器 64, 65, 66. 67からの出力 データを （ o , 0 OH, 0 OH. 00H) とすると、 データ p0I は次 式で表わすことができる。
Figure imgf000062_0001
これは表 5のステップ S 2006に対応する。
次に、 ステップ S54において、 キュー書き込みカウンタの計数値 c n t WQを 1だけインクリメン卜する。 つまり、 キュー書き込みカウンタの 計数値 c n tWQは 2になる。 次いで、 ステップ S 55において、 キュー 書き込みカウンタの計数値 c n tWQがキュー書き込み数 nQより小さい 場合はステップ S 52に戻り、 そうでない場合はサブルーチン処理 P 3を 終了してリターンする。 この場合、 キュー謇き込みカウンタの計数値 c n tWQは 2であり、 キュー書き込み数 nQは 2であるから、 サブルーチン 処理 P 3を終了して、 図 8のサブルーチン処理 P 1にリターンする。
図 8のステップ S 38において、 情報シンボルカウンタの計数値 c n t を 1だけィンクリメントする。 この場合、 情 ¾シンボルカウンタの計数値 c n tは 1になる。 次いで、 ステップ S 39において、 惰報シンボルカウ ンタの計数値 c n tが情報シンボル数 n I n f oより小さい場合はステツ ブ S 32に戻る一方、 そうでない場合はサブルーチン処理 P 1を終了する < この場合、 惰報シンボルカウンタの計数値 en ΐは 1であり、 情報シンポ ル数 n I n f 0は 10であるから、 ステップ S 32に戻る。
ステップ S 32において、 符号語バッファから情報シンボルカウンタの 計数値 cn t番目の情報シンボルつまり Bu f B [c n t] を読み出す。 この場合、 情報シンボルカウンタの計数値 c n tは 1であるから、 符号語 バッファの先頭から 2番目のシンボルである。 ここで取り出した 2番目の 情報シンボルをデータ i 0fllとする。 次いで、 ステップ S33において、 32ビッ トラツチ 73から 32ビッ トのデータを読み出し、 その上位から i nd e x (本動作例の場合は 1) バイ ト目、 つまり上位 8ビッ トを得る。 この場合、 32ビッ トラッチ 73の内容は、 データ （P 004, 00H. 0 0H, 00H) であるので、 その上位 8ビッ トのデータは P otMである。 これは表 5のステップ S 2007に対応する。 次いで、 ステップ S 34に おいて、 32ビッ トラッチ 69の内容を 0にクリアする。 これは表 5のス テツブ S 2008に対応する。
さらに、 ステップ S 35において、 キューメモリ 72の内容を、 キュー メモリ 72のフィード回数 n F e e d回だけ進めるサブルーチン処理 P 2 を実行する。 当該サブルーチン処理 P 2では、 上記の処理と同様にしてキ: 一メモリ 72を 1回だけ進める。 これは表 5のステップ S 2009に対応 する。 そして、 図 8のステップ S 36において、 入力データとステップ S 33で求めた 32ビッ トラツチ 73の上位 8ビッ 卜のデータとの排他的論 理和を求める。 このデータ値を d。01とすると、 この場合、 入力データ i 0 01とデータ！)。 0<との排他的論理和なので、 データ d。 は次式で表わすこ とができる。
Figure imgf000064_0001
次に、 ステップ S37において、 ステップ S 36で求めたデータ値と生 成多項式の各係数との積をキューメモリ 72に著き込むサブルーチン処理 P 3を実行する。 以下、 そのサブルーチン処理 P 3を図 10を参照して具 体的に ίίέ明する。
まず、 図 10のステップ S δ 1において、 キュー書き込みカウンタの計 数値 c n tWQを 0に初期化し、 ステップ S 52において、 ステップ S3 6で求めたデータ d eo,と生成多項式 （式 （34) ) の係数とのガロア体 上の積を、 4シンボル （32ビッ 卜） だけ求める。 その際に、 ガロア体演 算テーブルを用いるが、 キュー香き込みカウンタの計数値 c n tWQが 0 の時には、 生成多項式 （式 （34) ) の係数として ks. k 4. k 3, k 2が 選ばれる。 さらに、 ステップ S 53において、 ステップ S 52で求めた結 果データをキューメモリ 72に書き込む。 このとき、 32ビッ トラッチ 7 5は、 データ （P OO Di P 001， 002' P 003 ) を出力しており、 8ビッ ト ラッチ 68はデータ 00Hを出力しているので、 排他的論理和演算器 64, 65. 66. 67の入力データは、 データ （0 OH. p0oo. p001. 00 2) と、 データ （k 5 · d 001 » k 2 · d 001 ) で ある。 従って、 排他的論理和演算器 64, 65. 66， 67の出力データ を （P 005. P O 0 B. P 0 D7. P οοβ) とすると、 この出力ァ一夕は、 次式で 表わすことができる。
( 005. Ρ 006. Ρ 007. Ρ θ08ノ
= ( k 5 " α 001 > k * α 001 + P 00 D.
k 3 ' a 001 + P 001. k 2 · a oin+ p oo2) … ( 1 ) これは表 5のステップ S 2010に対応する。 次に、 ステップ S 54において、 キュー害き込みカウンタの計数値 c n tWQを 1だけインクリメントする。 つまり、 キュー香き込みカウンタの 計数値 c n tWQは 1になる。 次いで、 ステップ S 55において、 キュー 謇き込みカウンタの計数値 c n t WQがキュー書き込み数 n Qより小さい 場合はステップ S 52に戻る一方、 そうでない場合はサブルーチン処理 P 3を終了する。 この場合、 キュー害き込みカウンタの計数値 c n tWQは 1であり、 かつキュー害き込み数 n Qは 2であるから、 ステップ S 52に 民る 0
ステップ S δ 2において、 ステップ S 56で求めたデータ d。(πと生成 多項式 （式 （34) ) の係数とのガロア体上の積を、 4シンボル （32ビッ ト） だけ求める。 その際に、 ガロア体演算テーブルを用いるが、 キュー誊 き込みカウンタの計数値 c n tWQが 1の時には、 生成多項式 （式 （14) ) の係数として 0, 0. 0が選ばれる。 次いで、 ステップ S 53に おいて、 S 52で求めた結果データをキューメモリ 72に香き込む。 この とき、 32ビッ トラッチ 75は、 データ （P otH. 0 OH. 0 OH. 00 H) を出力しており、 8ビッ トラツチ 68は p。03を出力しているので、 排他的論理和演算器 64， 65. 66, 67の入力データは、 データ （p cos. P 004, 00H, 0 OH) と、 データ （k , · d 001, 0 OH. 0 OH. 0 OH) である。 従って、 排他的論理和演算器 64, 65. 66, 67の出力データをデータ （p ooe, P oo*. 0 OH, 00H) とすると、 データ！）。οβは次式で表わすことができる。
· dooi+ P oo3 3 o これは表 5のステップ S 2011に対応する。
次に、 図 10のステップ S 54において、 キュー書き込みカウンタの計 数値 c n tWQを 1だけインクリメン卜する。 つまり、 キュー窨き込み力 ゥン夕の計数値 c n tWQは 2になる。 次いで、 ステップ S δ 5において、 キュー書き込みカウンタの計数値 c n tWQがキュー害き込み nQより小 さい場合はステップ S 52に戻る一方、 そうでない場合はサブルーチン処 理 P3を終了してリターンする。 この場合、 キュー害き込みカウンタの計 数値 c n tWQは 2であり、 キュー書き込み数 nQは 2であるから、 サブ ルーチン処理 P 3を終了して、 図 8のサブルーチン処理 P 1に戻る。
図 8のステップ S38において、 惰報シンボルカウンタの計数値 c n t を 1だけインクリメントする。 つまり、 情報シン'ボルカウンタの計数値 c n tは 2になる。 次いで、 ステップ S 39において、 情報シンボルカウン タの計数値 cn tが情報シンボル数 n I n f oより小さい場合はステップ S 32に戻る一方、 そうでない場合はサブルーチン処理 P 1を終了してリ ターンする。 この場合、 情報シンボルカウンタの計数値 c n tは 2であり、 情報シンボル数 n I n f 0は 10であるから、 ステップ S 32に戻る。 ステップ S 32において、 作業用 RAM63内の符号語バッファから情 報シンボルカウンタの計数値 c n t番目の情報シンボル B u f B [c n t] を読み出す。 この場合、 情報シンボルカウンタの計数値 cn tは 2である から、 符号語バッファの先頭から 3番目のシンボルである。 ここで取り出 した 3番目の情報シンボルをデータ i。02とする。 次いで、 ステップ S 3 3において、 32ビッ トラッチ 73から 32ビッ 卜のデータを取り出し、 その上位から i nd ex (本動作例の場合は 1 ) バイ ト目、 つまり上位 8 ビッ 卜のデータを得る。 この場合、 32ビッ トラツチ 73の内容は 〔p00 β, p oo4. 0 OH. 0 OH) であるので、 その上位 8ビッ トのデータは P 009である。 これは表 5のステップ S 2012に対応する。 さらに、 ステツ ブ S 34において、 32ビッ トラッチ 69の内容を 0にクリアする。 これ は表 5のステップ S 2013に対応する。 次いで、 ステップ S 35において、 キューメモリ 72の内容を、 キュー メモリ 72のフィード回数 n Fe e d回だけ進めるサブルーチン処理 P 2 を実行する。 当該サブルーチン処理 P 2では、 上記の処理と同様にしてキュ 一メモリ 72を 1回だけ進める。 これは表 5のステップ S 2014に対応 する。
次いで、 図 8のステップ S 36において、 入力データとステップ S 33 で求めた 32ビッ トラツチ 73の上位 8ビッ トのデータとの排他的論理和 を求める。 このデータ値を d tiozとすると、 この場合、 入力データ i。02と データ P。 との排他的論理和なので、 データ d。02は次式で表わすことが できる。
d 002 = 1 002 + P 009 … ^ 9 ) 以下、 上記の処理と同様に、 ステップ S37、 S 38、 S 39と進み、 さらに、 情報シンボルカウンタの計数値 cn tが情報シンボル数 n I n f o (本動作例において、 n I n f o= 10である。 ） に一致するまでステツ ブ S 32からステップ S 39までの処理を繰り返し、 サブルーチン処理 P 1を終了して、 図 7のメインルーチンに戻る。
次いで、 図 7のステップ S 22において、 キューメモリ 72から溢れた 32ビッ トのデータをダミーデータとして読み出す。 これは表 5のステツ ブ S 2052に対応する。 次いで、 ステップ S 23において、 キューメモ リ 72の内容を、 キューメモリ 72のフィード回数 nF e e d回だけ進め るサブルーチン処理 P 2を実行する。 当該サブルーチン処理 P 2では、 上 記の処理と同様にしてキューメモリ 72を 1回だけ進める。 これは表 5の ステップ S 2053に対応する。
次に、 図 7のステップ S 24において、 キューメモリ 72からパリティ シンボルを 4シンボルずつ合計 n Pa r i t yシンボル読み出し、 作業用 RAM63内の符号語バッファ B u ί B [] のパリティ語領域に格納する サブルーチン処理 P 4を実行する。 次に、 当該サブルーチン処理 P 4の内 容を図 11を参照して具体的に説明する。
まず、 図 11のステップ S 61において、 キュー読み出しカウン夕の計 数値 cn tRQを 0に初期化し、 ステップ S62において、 キューメモリ 72からパリティ シンボルを 4シンボルずつ読み出す。 さらに、 ステップ
563において、 作業用 R A M 63内の符号語バッファのパリティ語領域 に、 ステップ S 62で読み出した 4シンボル （32ビッ ト） 分のパリティ シンボルを格钠する。 この場合、 情報シンボル数 n I n f 0は 10であり、 キュー銃み出しカウンタの計数値 c n tRQは 0であるから、 符号語バッ ファに格納する位置 B u f B [n I n f 0 + c n t RQ · 4, ···, n I n f o + cn tRQ - 4 + 3] は Bu f B [10, -, 13] となる。 そし て、 ステップ S 64において、 キュー読み出しカウンタの計数値 c n t R Qを 1だけインクリメントする。 この場合、 計数値 c n t RQは 1になる。 次いで、 ステップ S 65において、 キュー銃み出しカウンタの計数値 c n t RQがキュー書き込み回数 nQより小さい場合、 ステップ S 62に戻る —方、 そうでない場合、 サブルーチン処理 P4を終了してリターンする。 この場合、 計数値 cn 11¾0は1でぁり、 キュー書き込み回数 nQは 2で あるから、 ステップ S 62に戻る。
ステップ S 62において、 キューメモリ 72からノくリティシンボルを 4 シンボルずつ銃み出し、 次いで、 ステップ S 63において、 作業用 RAM
63内の符号語バッファのパリティ語領域に、 ステップ S 62で読み出し た 4シンボル （32ビッ ト） 分のパリティシンボルを格納する。 この場合、 情報シンボル数 n I n f 0は 10であり、 キュー読み出しカウンタの計数 値 cn tRQは 1であるから、 符号語バッファに格納する位置 B u f B [n I n f o + cn tRQ - 4, ···. n I n f o + cn tRQ - 4 + 3] は B u f B [14. ···， 17] となる。 さらに、 ステップ S64において、 キュ 一読み出しカウンタの計数値 c n t RQを 1だけインクリメントする。 こ の場合、 計数値 c n t RQは 2になる。 次いで、 ステップ S 65において、 キュー読み出しカウンタの計数値 c n t RQがキュー書き込み回数 nQよ り小さい場合、 ステップ S 62に戻る一方、 そうでない場合、 サブルーチ ン処理 P 4を終了してリターンする。 この場合、 計数値 c n t RQは 2で あり、 キュー害き込み回数 nQは 2であるから、 サブルーチン処理 P 4を 終了してメインルーチンにリターンする。 このサブルーチン処理 P 4は、 表 5のステップ S 2054及び S 2055に対応する。
以上で、 本動作例である RS (15, 10, d = 6) の符号語生成処理 を終了する。 ただし、 符号語は符号語バッファ Bu f B [0. ···, n I n f o + nPa r i t y-1] に格納されている。 この場合、 情報シンボル 数 n I n f oは 10であり、 ノ、 'リティシンボル数 nPa r i t yは 5であ るから、 苻号語は符号語バッファ Bu f B [0, ···, 14〕 に格納されて いる。
当該第 2の本実施形態においては、 第 1の実施形態に示した効果に加え て以下のような効果が得られる。 入力データと生成多項式の各係数とのガ ロア体上の積データを予め演算して ROM71に格納され、 初期化処理時 に作業用 RAM63に転送され、 作業用 RAM63は係数記慷手段を構成 する.。 図 3及び図 4の回路装置では、 係数記憶手段である作業用 RAM 6 3から同時に 4シンボルの積データを読み出すことができるように構成さ れる。 また、 m段の 32ビッ トラッチ 72— 1乃至 72— mからなるキュ 一メモリ 72を用いて、 第 1の記慷手段と選択手段を実現する一方、 8ビッ トラツチ 68を用いて、 第 2の記慷手段を実現する。 さらに、 8ビッ ト排 他的論理和澳算器 64, 65, 66. 67を用いて、 排他的論理和演算手 段を実現し、 また、 R0M71に格納されたプログラムを実行する CPU 61とラツチ制御装置 62とを用いて、 読み出し制御手段と第 1と第 2の 選択手段を実現する。
従って、 誤り訂正符号化装置の回路構成を従来技術に比較して簡単化す ることができるとともに、 リード ' ソロモン符号 RS (n, n— P, d = P + l) を、 1以上 4 xm以下である任意の Pについて符号化できる。 例 えば、 m=l 6とすると、 最小符号間距離 dを 2から 65まで自由に設定 できる。 ここで、 ガロア体上の積データを含むガロア体演算テーブルは、 初期化処理において、 ROM71から作業用 RAM63上に転送されて設 定されるので、 上記初期化処理において、 転送する種データを変更しかつ 初期化のパラメータ （本実施形態においては、 32ビッ トラッチの数 nQ u e u e L a t c hと、 パリティシンボル数 n P a r i t yである。 ） を 変更することにより、 装置の回路構成を変えずに、 原始多項式の変更ゃ符 号語の最小符号間距離 dの変更が可能である。 また、 符号語バッファを作 業用 RAM63上に有しているので、 ROM71に格納されるプログラム において、 情報シンボルの取り込み処理の内容とパリティ シンボル格納処 理の内容を変更することによって、 種々の積符号などの誤り訂正符号を符 号化することかできる。 また、 このようなプログラムの変更を行うと、 L DCと積符号の切り換えも、 装置の回路橇成を変えずに行えるという特有 の効果を有する。 <第 3の実施形態〉
図 15は、 本発明に係る第 3の実施形態の誤り訂正復号化装置の構成を 示すブロック図である。 図 15に示すように、 この第 3の実施形態の誤り 訂正複号化装置は、
( a ) 図 3に示す誤り訂正符号化装置と同様の構成を有する剰余演算器 2 08と、
(b)誤り数値及び誤り位置演算器 209と、
(c) 受信語記憶装置読み出しコントローラ 210と、
(d)排他的論理和演算器 211と、
( e〕 受信語記憶装置書き込みコン卜ローラ 212と、
(f )複数 N個のラッチが縱続接続されたシフ トレジスタからなる受信語 記億装置 213とを備える。
以下、 図 15を参照してリード · ソロモン符号 RS (N, -2 t, d =2 t + 1) の誤り訂正処理について説明する。
まず、 シンドロームを演算する処理を述べる。 リード . ソロモン符号 R S (N. N-2 t. d = 2 t + 1) の生成多項式は次式で表わすことがで きる。
G (X) = (X一な0) (Χ-α1) … (Χ-α21-1) … (40) ここで、 受信すべき符号語 Αを符号シンボル a ,の列として次式で表し、 A= ( a 0. i, a 2. ··'. a … (41) 受信時の誤りパターン Eを誤りシンボル e ,の列として次式で表し、
E= (e 0, e i, e 2, -, e n -!) … (42) 受信語 Yを受信シンボル y iの列として次式で表すとき、
Y= (yo, y y 2. ·'·, y n-i) ··· (43) 符号多項式 A (X) を A (X) -ao+a, · X+a X2 +〜+an-1 · χ η·1 … （44) とし、 誤り多項式 E (X) を
E (X) eo+ei · X+e2' X2十… + 6 "-! · X11-1 - (45) とし、 受信多項式 Y (X) を
Y (X) =y。+y , · X + y 2 · X2 +… +yn-, · Xn-】 … （46) と定義する。 受信語 Υは受信すべき符号語 Αに対して誤りパターン Εが加 わったものであるから、 受信多項式 Y (X) は、
Y (X) =A (X) +E (X) … (47) と表わすことができる。 ここで、 剰余多項式 r (X) を
r (X) = [Y (X) ] MOD G (X) … (48) として定¾する。 ここで、 A MOD Bは Aを Bで除算したときの剰余 を演算する演算子である。 符号語 A (X) は生成多項式 G (X) で割り切 れるので、 式 （47) 及び式 （48) から次式を得る。
r (X) = [E (X) ] MOD G (X) … (49) また、 式 （49) を展開した次式
r (X) = Γ 0+ Γ ! · X+r2- …+！^ · X2t -1… （50) を用いて、 剰余多項式 r (X) の各係数 r。. r i. r 2. ···. r st を並 ベたべク トル表現である剰余べク トルを次式で表わす。
r = (r 0. rlt r 2, …， r 2,-,) … (51) 剰余多項式 r (X) は、 受信多項式 Y (X) を生成多項式 G (X) で割- た余りであるから、 情報多項式 I (X) を生成多項式 G (X) で割った余 りであるパリティ多項式 R (X) を求める方法と同じ方法で求められるこ とがわかる。 つまり、 誤り訂正符号化装置に受信語 Yを入力すると、 入力 された受信語 Yを生成多項式 G (X) で割ったときの剰余としてパリティ 語の代わりに剰余べク トノレ 1"カ<得られる。 以上説明したように、 剰余演算器 208として、 第 2の実施形態の誤り 訂正符号化装置を用いることができる。 剰余べク トル rを得ると、 例えば、 次式を用いて、
2t-l
S (X) = ∑ [ (G (X) — G {a ') ) / (Χ-α ')
i =0
··· (52) 一般化シン ドローム S (X) を演算することができる （例えば、 従来技術 文献 「荒木純道 （Kiyomichi Araki) ほか， "リード . ソロモン符号の復 号のための一般化シンドローム多項式" ， 1991年電子情報通信学会春 季全国大会， A— 278, p p. 1 - 280. 1991年」 参照。 ） 。 従つ て、 第 2の実施形態の誤り訂正符号化装置である剰余演算器 208に受信 語 Yを入力し、 式 （52) の演算を行うことによって、 出力として一般化 シンドローム S CX) が得られる。
次いで、 誤り数値及び誤り位置を求める処理について述べる。 ここで、 誤りが L個の位置 （j i, j 2. -. j L) に生じたと仮定して説明する。 ここで、 L≤ tであり、 0≤ j！く j 2く…く j L≤n— 1とする。
式 （52) より、 We 1 c hと B e r 1 e k ampの方法 （例えば、 米 国特許第 4, 633. 470号参照。 ） や公知のユークリッ ド互除法等を 用いて誤り数値と誤り位置の組 （e ,n, j n) , n = l, 2, ···, Lを求 めることができる。 誤り数値及び誤り位置演算器 209には、 剰余演算器 208から剰余べク トル rが入力され、 誤り数値及び誤り位置演算器 20 9は、 上記の公知の方法によって、 誤り数値と誤り位置の組 （e ,n, j ,) を求め、 その誤り数値と誤り位置の組 （e in, j n) を η = 1から n==L (L≤ t) まで誤り個数だけ順次出力する。 ここで、 誤り数値のデータは 排他的論理和演算器 2 1 1の第 2の入力端子に出力される一方、 誤り位置 のデータはァドレスとして受信語記憶装置銃み出しコントローラ 2 1 0及 び受信語記 «装置香き込みコントローラ 2 1 2に出力される。
さらに、 誤り訂正処理について述べる。 誤り数値及び誤り位置演算器 2 0 9は誤り数値と誤り位置の組 （e i n, j n) を出力するが、 その誤り位 置 j πに位置する受信シンボル y に誤り数値 e ί ηを加えることにより、 誤りを訂正する。 そのために、 以下の処理を実行する。 まず、 受信語記憶 装置 2 1 3のデータ読み出し動作を制御する受信語記憶装置読み出しコン トローラ 2 1 0にァドレスとして誤り位置 j <>を入力して、 誤り位置 j。に 位置する受信シンボル y を受信語記憶装置 2 1 3から読み出す。 その読 み出した受信シンボル y j nと、 それに対応する誤り数値 e i nとを、 排他的 論理和演算器 2 1 1に入力することにより、 受信シンボル y i nと誤り数値 e の和 y + e i nをその出力データとして得る。 この出力データ y e ,„が訂正後の符号シンボル a となるので、 この訂正後の符号シンボル a i nを、 元の誤り位置 j nを了ドレスとし、 受信語記憶装置 2 1 3のデー タ書き込み動作を制御する受信語記憶装置害き込みコントローラ 2 1 2を 用いて、 受信語記悚装置 2 1 3に害き込む。 以上の処理を、 誤り数値及び 誤り位置演算器 2 0 9が、 n = lから n = L { L≤ t ) まで順次誤り数値 と誤り位置の組 （e j。） を出力することによって繰り返すことによ り、 すべての受信語に対して誤り訂正を実行して誤り復号化処理を完了す るこ.とができる。 このとき、 受信語記憶装置 2 1 3において、 誤り訂正さ れた符号語 Aを得ることができる。 そして、 当該符号語 Aは、 受信語記憶 装置 2 1 3のァ ドレスを順次ィンクリメ ントしながら、 受信語記憶装置読 み出しコントローラ 2 1 0に入力することにより、 受信語記憶装置読み出 しコントローラ 2 1 0により、 読み出されて誤り訂正された出力データと して出力される。
以上説明したように、 第 3の実施形態によれば、 第 2の実施形態の誤り 訂正符号化装置を用いて誤り訂正復号化装置を実現することができる。 従つ て、 第 1及び第 2の実施形態と同様に、 従来技術の装置に比較して回路構 成が簡単であって、 回路構成を変更することなく、 実用に供することかで きる復号化速度を有して、 種々の最小符号間距離を有する誤り訂正符号を 復号化することができる誤り訂正復号化装置を実現することができる。 ぐ変形例〉
以上の実施形態において、 誤り訂正符号化装置を以下のように構成して もよい。 すなわち、 変形例の誤り訂正符号化装置は、 2 Nの元の数を有す るガロア体 G F ( 2 s) 上の元を有するリード . ソロモン符号を用いて、 1シンボル当たり自然数 Nビッ 卜の入力データに対する誤り訂正符号を符 号化する誤り訂正符号化装置において、
各入力データと上記リード · ソロモン符号の生成多項式の各係数とのガ ロア体上の複数の «デ一タをそれぞれ予め演算して、 上記複数の積データ を、 各ァドレスに対して複数 b個の積データを 1組として予め記憶する積 データ記憶手段と、
それぞれ N x bビッ 卜の記憶容量を有する自然数 m個の記憶装置からな る第 1の記馕手段と、
入力データに応答して、 上記檳データ記憶手段に記億された複数の穣デ ータを、 複数 b個の穣データを 1組として並列に読み出すように上記積デ 一夕記憶手段を制御する読み出し制御手段と、
それぞれ N x bビッ 卜の第 1と第 2の入力端子を有し、 上記読み出し制 御手段によって上記積データ記憶手段から並列に銃み出される複数 b個の 積データが第 1の入力端子に入力され、 上記第 1の入力端子に入力される データと、 上記第 1の入力端子に入力されるデータとの排他的論理和を演 算して演算結果のデータを出力する排他的論理和演算手段と、
上記 m個の記慷装置に記憶されたデータを 1つの記憶装 毎に選択的に 順次読み出して出力し、 上記選択的に読み出して出力される Nx bビッ ト のデータのうち上位 Nx (b— 1) ビッ トのデータを上記排他的論理和演 算手段の第 2の入力端子の下位 Nx (b— 1) ビッ トに出力するとともに、 上記排他的論理和演算手段から出力される演算結果のデータを、 上記 m個 の記慷装置のうちの 1つに選択的に順次切り換えて害き込むように、 上記 第 1の記憶手段を制御する第 1の選択手段と、
Nビッ 卜の記億容量を有し、 上記第 1の選択手段によって上記 m個の記 憶装 Sのうちの 1つから選択的に出力される Nxbビッ 卜のデータのうち 下位 Nビッ 卜のデータを一時的に記悚して上記排他的論理和演算手段の第 2の入力端子の上位 Nビッ 卜に出力する第 2の記憶手段と、
上記入力データを上記積データ記境手段に順次入力することにより、 上 記第 1の記憶手段の m個の記憶装置においてパリティデータを生成し、 上 記入力データに続いて、 上記 m個の記憶装置を 1つの記慷装置毎に選択的 に順次切り換えることにより、 上記 m個の記悚装置において生成される各 パリティデータを順次出力する第 2の選択手段とを備える。 なお、 図 1及 び図 4の実施形態においては、 N=8、 b = 4、 及び m=3である。
以上の実施形態において、 穣データを記億するために ROM14を用い ている力、 本発明はこれに限らず、 ROM14に代えて、 論理回路素子の 組み合わせによる論理回路により構成され、 入力データに対して積データ を演算する演算手段を用いてもよい。
産業上の利用可能性
本発明によれば、 2Nの元の数を有するガロア体 GF (2N) 上の元を有 するリード ' ソロモン符号を用いて、 1シンボル当たり自然数 Nビッ トの 入力データに対する誤り訂正符号を符号化する誤り訂正符号化装置及び方 法において、 稹データ記慷手段である ROM (14) は、 各入力データと 上記リード · ソロモン符号の生成多項式の各係数とのガロア体上の複数の 積データをそれぞれ予め演算して、 上記複数の積データを、 各ァドレスに 対して複数 b個の積データを 1組として予め記憶する。 読み出し制御手段 (12, 13, 24- 26, 28 ) は、 入力データに応答して、 R OM ( 1 4) に記億された複数の積データを、 上記複数 b個の積データを 1組とし て並列に読み出した後、 排他的論理和演算器 （15— 18) 及びバス ¾択 器 （19) を介して自然数 m個の記憶装置 （20— 22) に選択的に順次 さき込む。 入力データを ROM (14) に順次入力することにより、 m個 の記愫装置においてパリティデータを生成して出力する。
従って、 複数の稹データを記憶した ROM 14から 4個の積データを 1 組として並列に （同時に） 排他的論理和演算器 （15— 18) に対して読 み出し可能に構成し、 4個の積データを用いて同時に処理し、 かつ 3個の 32ビッ トラッチ （20— 22) を選択的に順次繰り返して使用すること により、 符号化処理の演算をしているので、 回路構成を、 図 14の従来技 術の誤り訂正符号化装置の回路構成に比較して極めて簡単にすることがで きるとともに、 効率的にかつ高速で演算することができ、 実用に供するこ とが可能な符号化速度で誤り訂正符号を符号化することができる。
また、 本発明に係る上記誤り訂正符号化装置を用いて誤り訂正復号化装 置を構成することにより、 回路構成を極めて簡単にすることができるとと もに、 効率的にかつ高速で演算することができ、 実用に供することが可能 な復号化速度で誤り訂正符号を復号化することができる。

Claims

請 求 の 範 囲
1 . 2 Nの元の数を有するガロア体 G F ( 2 N) 上の元を有するリード · ソ ロモン符号を用いて、 1シンボル当たり自然数 Nビッ 卜の入力データに対 する誤り訂正符号を符号化する誤り訂正符号化装置において、
各入力デー夕と上記リード · ソロモン苻号の生成多項式の各係数とのガ ロア体上の複数の種データをそれぞれ予め演算して、 上記複数の積データ を、 各ァドレスに対して複数 b個の積データを 1組として予め記慷する種 データ記馊手段と、
それぞれ N x bビッ 卜の記憶容量を有する自然数 m個の記憶装置からな る第 1の記慷手段と、
入力データに応答して、 上記積データ記憶手段に記憶された複数の積デ 一夕を、 複数 b個の穰データを 1組として並列に読み出すように上記積デ 一タ記憧手段を制御する読み出し制御手段と、
それぞれ N x bビッ トの第 1と第 2の入力端子を有し、 上記読み出し制 御手段によって上記積データ記憶手段から並列に読み出される複数 b個の 積データが第 1の入力端子に入力され、 上記第 1の入力端子に入力される データと、 上記第 2の入力端子に入力されるデータとの排他的論理和を演 算して演算結果のデータを出力する排他的論理和演算手段と、
上記 m個の記憶装置に記憶されたデータを 1つの記憶装置毎に選択的に 順次読み出して出力し、 上記選択的に読み出して出力される N x bビッ ト のデータのうち上位 N x ( b— 1 ) ビッ トのデータを上記排他的論理和演 算手段の第 2の入力端子の下位 N x ( b— 1 ) ビッ トに出力するとともに、 上記排他的論理和演算手段から出力される演算結果のデータを、 上記 m個 の記憶装置のうちの 1つに選択的に順次切り換えて香き込むように、 上記 第 1の記 ¾手段を制御する第 1の選択手段と、 Nビッ 卜の記憶容量を有し、 上記第 1の:! M択手段によって上記 m個の記 慷装置のうちの 1つから選択的に出力される N x bビッ 卜のデータのうち 下位 Nビッ トのデータを一時的に記憶して上記排他的論理和演算手段の第 2の入力端子の上位 Nビッ 卜に出力する第 2の記憶手段と、
上記入力データを上記積データ記憶手段に順次入力することにより、 上 記第 1の記億手段の m個の記憶装置においてパリティデータを生成し、 上 記入力データに続いて、 上記 m個の記憶装置を 1つの記慷装置毎に選択的 に順次切り換えることにより、 上記 m個の記憶装置において生成される各 パリティデータを順次出力する第 2の選択手段とを備えたことを特徴とす る誤り訂正符号化装置。
2. 上記読み出し制御手段と、 上記第 1の選択手段と、 上記第 2の選択手 段とは、 別の記憶装置に記使された所定のプログラムを実行する中央演算 制御装置によつて構成されたことを特徴とする請求項 1記載の誤り訂正符 号化装置。
3. 2 Nの元の数を有するガロア体 G F ( 2 ') 上の元を有するリード · ソ ロモン符号を用いて、 1シンボル当たり自然数 Νビッ トの入力データに対 して符号化された誤り訂正符号を復号化する誤り訂正復号化装 Sにおいて、 上記入力データと、 上記入力データに対するパリティデータとを含む複 数の受信シンボルからなり、 入力される受信語を各受信シンボル毎に記憶 する受信語記憶手段と、
請求項 1記載の誤り訂正符号化装置を備え、 上記リード ' ソロモン符号 の生成多項式を用いて、 上記入力される受信語に対する剰余を演算して出 力する剰余演算手段と、
上記剰余演算手段から出力される剰余に基づいて、 上記受信語における 誤り 置と、 上記誤り位置に対応する誤り数値との組を演算して出力する 誤り数値及び誤り位置壙算手段と、
上記誤り数値及び誤り位置演算手段から出力される上記受信語における 誤り位匱に基づいて、 上記受信語記慷手段に記億された上記誤り位置にお ける受信シンボルを上記受信語記憶手段から読み出して出力する銃み出し 制御手段と、
上記読み出し制御手段から出力される上記誤り位置における受信シンボ ルと、 上記誤り数値及び誤り位置演算手段から出力される、 上記誤り位置 に対応する誤り数値との排他的論理和を演算して、 演算結果のデータを出 力する排他的論理和演算手段と、
上記排他的論理和演算手段から出力される演算結果のデータを、 上記受 信語記憧手段の上記誤り位置に書き込むことにより、 上記誤り位置におけ る受信シンボルを訂正する書き込み制御手段とを備えたことを特徴とする 誤り訂正復号化装置。
4. 2 Nの元の数を有するガロア体 G F ( 2 K) 上の元を有するリード . ソ ロモン符号を用いて、 1シンボル当たり自然数 Νビッ 卜の入力データに対 する誤り訂正苻号を符号化する誤り訂正符号化方法において、
各入力データと上記リード · ソロモン符号の生成多項式の各係数とのガ ロア体上の複数の積データをそれぞれ予め演算して、 上記複数の積データ を、 各ァドレスに対して複数 b個の積データを 1組として積データ記愴手 段に予め記馊するステップと、
入力データに応答して、 上記積データ記憶手段に記慷された複数の積デ 一夕を、 複数 b個の積データを 1組として並列に読み出すように上記積デ 一夕記憶手段を制御するステッブと、
それぞれ N x bビッ 卜の第 1と第 2の入力端子を有する排他的論理和演 算手段を用いて、 上記積データ記憧手段から並列に読み出される複数 b個 の積データが第 1の入力端子に入力され、 上記第 1の入力端子に入力され るデータと、 上記第 2の入力端子に入力されるデータとの排他的論理和を 演算して演算結果のデータを出力するステップと、
それぞれ N x bビッ 卜の記憶容量を有する m個の記億装置の第 1の記憶 手段に記憧されたデータを 1つの記憶装置毎に選択的に順次読み出して出 力し、 上記選択的に読み出して出力される N x bビッ 卜のデータのうち上 位 N x ( b— 1 ) ビッ トのデータを上記排他的論理和演算手段の第 2の入 力端子の下位 N x ( b - 1 ) ビッ トに出力するとともに、 上記排他的論理 和演算手段から出力される演算結果のデータを、 上記 m個の記憧,装置のう ちの 1つに選択的に順次切り換えて書き込むように、 上記第 1の記憶手段 を制御するステップと、
Nビッ 卜の記慷容量を有する第 2の記憶手段を用いて、 上記 m個の記慷 装置のうちの 1つから選択的に出力される N x bビッ 卜のデータのうち下 位 Nビッ トのデータを一時的に記憶して上記排他的論理和演算手段の第 2 の入力端子の上位 Nビッ 卜に出力するステップと、
上記入力データを上記穫データ記憶手段に順次入力することにより、 上 記第 1の記慷手段の m個の記憶装置においてパリティデータを生成し、 上 記入カデータに続いて、 上記 m個の記憶装置を 1つの記憶装置毎に選択的 に順次切り換えることにより、 上記 m個の記憶装置において生成される各 パリティデータを順次出力するステップとを含むことを特徴とする誤り訂 正符号化方法。
5 . 2 Nの元の数を有するガロア体 G F ( 2 W) 上の元を有するリード ' ソ ロモン符号を用いて、 1シンボル当たり自然数 Nビッ 卜の入力データに対 して符号化された誤り訂正符号を復号化する誤り訂正復号化方法において、 上記入力データと、 上記入力データに対するパリティデータとを含む複 数の受信シンボルからなり、 入力される受信語を各受信シンボル毎に受信 語記 it手段に記憶するステップと、
請求項 4記載の誤り訂正符号化方法により、 上記リード · ソロモン符号 の生成多項式を用いて、 上記入力される受信語に対する剰余を演算して出 力するステップと、
上記出力される剰余に基づいて、 上記受信語における誤り位置と、 上記 誤り位置に対応する誤り数値との組を演算して出力するステップと
上記出力される上記受信語における誤り位置に基づいて、 上記受信語記 慷手段に記 «された上記誤り位置における受信シンボルを上記受信語記愫 手段から読み出して出力するステップと、
上記出力される上記誤り位置における受信シンボルと、 上記出力される、 上記誤り位置に対応する誤り数値との排他的論理和を演算して、 演算結果 のデータを出力するステップと、
上記出力される演算結果のデータを、 上記受信語記憧手段の上記誤り位 置に書き込むことにより、 上記誤り位匿における受信シンボルを訂正する ステップとを含むことを特徴とする誤り訂正復号化方法。
PCT/JP1996/002866 1995-10-03 1996-10-02 Device and method for error correcting coding, and device and method for error correcting decoding Ceased WO1997013328A1 (en)

Priority Applications (4)

Application Number Priority Date Filing Date Title
US08/849,388 US5914969A (en) 1995-10-03 1996-10-02 Device and method for error correcting coding, and device and method for error correcting decoding
EP96932801A EP0806839B1 (en) 1995-10-03 1996-10-02 Device and method for error correcting coding, and device and method for error correcting decoding
DE69618930T DE69618930T2 (de) 1995-10-03 1996-10-02 Verfahren und vorrichtung zur fehlerkorrekturkodierung und-dekodierung
JP51415497A JP3622981B2 (ja) 1995-10-03 1996-10-02 誤り訂正符号化装置及び方法、並びに誤り訂正復号化装置及び方法

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP7/255991 1995-10-03
JP25599195 1995-10-03

Publications (1)

Publication Number Publication Date
WO1997013328A1 true WO1997013328A1 (en) 1997-04-10

Family

ID=17286386

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP1996/002866 Ceased WO1997013328A1 (en) 1995-10-03 1996-10-02 Device and method for error correcting coding, and device and method for error correcting decoding

Country Status (5)

Country Link
US (1) US5914969A (ja)
EP (1) EP0806839B1 (ja)
JP (1) JP3622981B2 (ja)
DE (1) DE69618930T2 (ja)
WO (1) WO1997013328A1 (ja)

Families Citing this family (14)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6253349B1 (en) * 1997-04-02 2001-06-26 Matsushita Electric Industrial Co., Ltd. Error detective information adding equipment
JP3238128B2 (ja) * 1998-06-02 2001-12-10 松下電器産業株式会社 リードソロモン符号化装置および方法
US6598201B1 (en) * 1999-03-15 2003-07-22 Texas Instruments Incorporated Error coding structure and method
US6360348B1 (en) * 1999-08-27 2002-03-19 Motorola, Inc. Method and apparatus for coding and decoding data
US8645803B2 (en) 2010-05-10 2014-02-04 Ternarylogic Llc Methods and systems for rapid error correction by forward and reverse determination of coding states
KR100918763B1 (ko) * 2003-11-14 2009-09-24 삼성전자주식회사 병렬 연접 저밀도 패리티 검사 부호를 사용하는 채널 부호화/복호 장치 및 방법
US7143333B2 (en) * 2004-08-09 2006-11-28 Motorola, Inc. Method and apparatus for encoding and decoding data
RU2365034C2 (ru) * 2004-08-12 2009-08-20 Моторола, Инк. Способ и устройство для кодирования и декодирования данных
DE05811730T1 (de) * 2004-12-15 2008-05-29 Nec Corp. Fehlerkorrekturkodiervorrichtung und dabei verwendetes fehlerkorrekturkodierverfahren
EP1850485A1 (en) * 2006-04-28 2007-10-31 Nokia Siemens Networks Gmbh & Co. Kg Method for encoding a data message K' for transmission from a sending station to a receiving station as well as method for decoding, sending station, receiving station and software
US9203438B2 (en) * 2006-07-12 2015-12-01 Ternarylogic Llc Error correction by symbol reconstruction in binary and multi-valued cyclic codes
US8201060B2 (en) * 2007-07-11 2012-06-12 Ternarylocig LLC Methods and systems for rapid error correction of Reed-Solomon codes
US10649841B2 (en) * 2018-03-05 2020-05-12 Alibaba Group Holding Limited Supporting multiple page lengths with unique error correction coding via galois field dimension folding
CN115113816B (zh) * 2022-06-24 2025-07-25 山东云海国创云计算装备产业创新中心有限公司 一种纠删码数据处理系统、方法、计算机设备及介质

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS61289731A (ja) * 1985-06-18 1986-12-19 Sanyo Electric Co Ltd Ｂｃｈ府号の復号方式
JPH04365139A (ja) * 1991-06-13 1992-12-17 Sharp Corp 誤り訂正処理用シンドローム演算回路

Family Cites Families (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4162480A (en) * 1977-01-28 1979-07-24 Cyclotomics, Inc. Galois field computer
US4410989A (en) * 1980-12-11 1983-10-18 Cyclotomics, Inc. Bit serial encoder
US4633470A (en) * 1983-09-27 1986-12-30 Cyclotomics, Inc. Error correction for algebraic block codes
US4649541A (en) * 1984-11-21 1987-03-10 The United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration Reed-Solomon decoder
US4928280A (en) * 1988-04-29 1990-05-22 International Business Machines Corporation Fast processor for multi-bit error correction codes
US4907233A (en) * 1988-05-18 1990-03-06 The United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration VLSI single-chip (255,223) Reed-Solomon encoder with interleaver
US5140596A (en) * 1990-02-20 1992-08-18 Eastman Kodak Company High speed encoder for non-systematic codes
JPH0774655A (ja) * 1993-09-03 1995-03-17 Toshiba Corp 誤り訂正符号化器

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS61289731A (ja) * 1985-06-18 1986-12-19 Sanyo Electric Co Ltd Ｂｃｈ府号の復号方式
JPH04365139A (ja) * 1991-06-13 1992-12-17 Sharp Corp 誤り訂正処理用シンドローム演算回路

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See also references of EP0806839A4 *

Also Published As

Publication number Publication date
US5914969A (en) 1999-06-22
DE69618930D1 (de) 2002-03-14
EP0806839A1 (en) 1997-11-12
DE69618930T2 (de) 2002-09-19
JP3622981B2 (ja) 2005-02-23
EP0806839A4 (en) 2000-12-13
EP0806839B1 (en) 2002-01-30

Similar Documents

Publication Publication Date Title
WO1997013328A1 (en) Device and method for error correcting coding, and device and method for error correcting decoding
US4649541A (en) Reed-Solomon decoder
US5170399A (en) Reed-Solomon Euclid algorithm decoder having a process configurable Euclid stack
JP2000508849A (ja) データ・ブロックの畳み込み符号化方法及び装置及び対応する復号方法及び装置
US5901158A (en) Error correction encoder/decoder
WO1999062183A1 (fr) Decodeur d&#39;image video pour code de convolution et procede de decodage d&#39;image video
EP1490977A2 (en) Apparatus for iterative hard-input forward error correction decoding
US5822337A (en) Programmable redundancy/syndrome generator
EP1225705A2 (en) Method and apparatus for encoding a product code
US6978415B1 (en) Variable redundancy cyclic code encoders
WO2002071625A1 (fr) Turbo decodeur, procede de turbo decodage et support de stockage dans lequel le procede est stocke
US7082564B2 (en) High throughput Reed-Solomon encoder
Cuevas et al. New architecture for high data rate turbo decoding of product codes
WO2001026235A1 (en) Interleave address generating device and interleave address generating method
JP3853439B2 (ja) 高速可変長コード復号化装置及び高速可変長コード復号化方法
US6405339B1 (en) Parallelized programmable encoder/syndrome generator
JP3888135B2 (ja) 誤り訂正符号復号装置
JP3429623B2 (ja) 高速可変長符号復号化装置
JPH0476540B2 (ja)
JPS60170330A (ja) 復号化システム
WO1999016175A1 (fr) Circuit integre a semi-conducteurs et systeme de traitement de donnees
JP2002118471A (ja) 記録再生装置及び誤り訂正符号化方法並びに情報記録方法
RU157943U1 (ru) Параллельный реконфигурируемый кодер бчх кодов
US6704901B1 (en) Runtime programmable Reed-Solomon decoder
KR102635135B1 (ko) 리드 솔로몬 디코더 및 이를 포함하는 반도체 장치

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): JP US

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): AT BE CH DE DK ES FI FR GB GR IE IT LU MC NL PT SE

WWE Wipo information: entry into national phase

Ref document number: 08849388

Country of ref document: US

WWE Wipo information: entry into national phase

Ref document number: 1996932801

Country of ref document: EP

121 Ep: the epo has been informed by wipo that ep was designated in this application
WWP Wipo information: published in national office

Ref document number: 1996932801

Country of ref document: EP

WWG Wipo information: grant in national office

Ref document number: 1996932801

Country of ref document: EP