Error detection/correction and fault detection/recovery – Pulse or data error handling – Error/fault detection technique
Reexamination Certificate
2000-04-06
2004-04-13
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Error/fault detection technique
C714S781000, C714S758000
Reexamination Certificate
active
06721919
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the circuit having encoder and decoder of error correction codes.
BACKGROUND OF THE INVENTION
Many error correction codes (ECC) currently used consist of linear codes or systematic codes. Systematic code is a category of code where data to be sent has a form of “original data +parity,” which is used in many application ECCs. These codes for ECC applications also incorporate Galois field or Galois extension fields which are a kind of number system used in the code.
For purposes of explanation of this invention it should be understood that word symbol length n (a symbol is data of 1 bit or multiple bits put together in a lump, and used as a synonym of byte or word), information word (message word or data word) symbol length k, generator matrix G (a matrix for calculating a parity by matrix operation on encoder) of linear code (n, k) on Galois extension field GF (2
m
) of m-bit symbol length or Galois field GF (2), and parity check matrix H (a matrix for calculating a syndrome on decoder), where G is a k×n matrix, and H is a (n−k)×n matrix. The syndrome information shows what and where an error has occurred in the data that must be calculated in a decoder.
An encoding calculation is performed for acquiring vG for the information word v (km bit) of symbol length k, and syndrome calculation in decoding is performed for acquiring wH
T
for received word w (nm bit) of symbol length n (where H
T
is a matrix of H). The above two calculations are both linear operations performed on GF (2
m
) or GF (2), and normally rendered a circuit by combining XOR gates in the form of XOR calculation. Each row vector of G and each row vector of H are linearly independent on GF (2
m
) or GF (2) respectively.
Systematic code includes the original information word in symbol k portion and also includes a parity word in the remaining symbol n−k portion.
In linear code and systematic code, of generator matrix of k×n matrix, the k×k area forms a unit matrix to embed an information word in the code word so that the process substantially performed in the encoder is applied only to an information word k×(n−k) matrix, of the generator matrix of k×n matrix, which generates a parity word. In the following description this k×(n−k) matrix will be referred to as G.
Depending on what circuit encodes and what syndrome calculation are to be performed, will determine whether the information word or received word is serial or parallel mode. If it is serial, it is implemented in a sequential circuit by using LFSR (Linear Feedback Shift Register, a kind of a shift register), etc. If the entire information word is in parallel mode, the word is encoded or decoded in parallel (hereafter, “parallel encoding/decoding”), it is implemented in a combinational circuit.
In the case where a decoder is implemented not in parallel encoding/decoding but in a sequential circuit (syndrome calculation and Chien search, for instance, are similar in circuit configuration) a method of sharing a register may be used. These are described in “Circuit for Generating Polynomials for Error Correction Calculation” (Japanese Unexamined Patent Publication No. Hei 3-190326), “Reed-Solomon Circuit for Decoding Error Correction Code” (Japanese Unexamined Patent Publication No. Hei 8-139612), and the following document: “An Area-Efficient VLSI Architecture of a Reed-Solomon Decoder/Encoder for Digital VCRs,” S. Kwon and H. Shin, IEEE trans. on Consumer Electronics, Vol.43, No.4, pp.1019-1027, November , 1997, etc.
In a combinational circuit, coordination of common portions (so called “Resource Sharing”) among multioutput logic functions includes a circuit design which performs the same calculation as separate circuits of the same system that are put together to act like a single circuit.
The method for using a decoder as an encoder for Reed-Solomon code is described in , “Use of the RS Decoder as an RS Encoder for Two Way Digital Communications and Storage Systems,” C. C. Hsu, I. S. Reed, and T. K. Truong, IEEE Transactions on Circuits and Systems for Video Technology, Vol.4, No.1, pp.91-92, February, 1994.
According to this article, it is a prerequisite to use a decoder with an erasure decoding feature, and indicates that it is difficult in a code such as Reed-Solomon code to correct erasure with parallel code. The problem in such a method is that encoding takes as long a time as decoding.
Parallel encoding/decoding is performed in the case where high speed is required and data is in parallel mode.
For example, in a memory system where:
(i) Error correction circuit of high speed and low power consumption for extending DRAM refresh time (QNVRAM)
where coordination of a group of encoders will be effective. Codes of different error correction capability should be concurrently used in order to improve flexibility and reliability of the system. (For example, see the specification of Japanese Unexamined Patent Publication No. Hei 10-13586.)
(ii) Error correction circuit for computer main storage that requires reliability (Memory ECC), where ECC is applied to memory in parallel encoding/decoding. In which case, the encoding should be performed at a high speed while error correction is slow.
(iii) Error correction code is used in a multiple manner in order to improve error correction capability, and if a high-speed decoding process is required in spite of originally slow data transfer speed.
For instance, in a future high-speed communication, etc. where there may arise the necessity to decrease packet retransmission by using a powerful ECC or to dynamically change error correction capability according to the situation, then effective coordination of a group of encoders is necessary.
Implementation of such parallel encoding/decoding circuit is equal to implementing a combinational circuit by deploying a sequential circuit, which generally makes circuit size much larger even though it depends on input word length and error correction capability. Thus, such parallel encoding/decoding could be performed only to code of low error correction capability. However, as implementable circuit size has increased in recent years, code allowing parallel encoding/decoding has also increased, heightening the importance of holding down the circuit size.
Also, each encoder must be made separately because the circuits of different error correction capability create the problem of a circuit becoming too large.
In addition, if information word length (data length) increases, it causes the corresponding problem of circuit size increasing.
SUMMARY OF THE INVENTION
An objective of the present invention is to improve a system having multiple encoders with varying maximum error correction capability, while reducing the size of the circuit by allowing most of the system to be shared among these encoders.
Another objective is to reduce the size of the system (combining encoders and decoders) by integrating circuits for parallel encoding/decoding and allowing sharing of most of the encoders and most of the syndrome generator in the decoders.
Further objective is to reduce the size of the circuit by holding down the extent of increase of the scale of the circuit even if information word length, (ie data length) has increased.
To attain these objectives, the present invention offers the following circuit.
An encoder capable of calculating parities of &agr; (where, &agr; is an integer of 2 or more) kinds of bit numbers with different error correction capability, comprising: a first circuit for generating a modified word by assigning a predetermined value to the input information word; a first circuit connected to the first circuit for generating intermediate signal “u” by linear operation using the modified word and matrix “P”; and a second circuit connected to the first circuit all or part of the intermediate signal and matrixes Q
1
, . . . , Q
&agr;
respectively.
A circuit having a single encoder and decoder capable of calculating parities of &agr; (here, &agr; is
Katayama Yasunao
Morioka Sumio
Britt Cynthia
De'cady Albert
Walsh Robert A.
LandOfFree
Shared encoder used in error correction having multiple... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Shared encoder used in error correction having multiple..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shared encoder used in error correction having multiple... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3249419