Geometry dash 2.1 sneak peek robot games
19 comments
Bitcoin maximum value
This invention was made with Government support under Contract No. The Government has certain rights in this invention. The present invention relates to a single bit error correction, double burst error detection technique and more particularly to a single bit error correction, double burst error detection code which may be used with RAMs Random Access Memories which experience single and adjacent bit errors due to the impingement of high energy particles.
A microprocessor executing software from RAMs can experience single and adjacent bit errors from high energy particles. Previous attempts to alleviate these errors involve using error correction codes. However, these error correction codes substantially increase the number of bits which must be added to the base microprocessor word width.
This both increases the amount of RAM memory needed as well as slowing the processing time due to the increased word length and increased processing time needed for error correction. There have been many previous attempts to formulate error correction codes, particularly single bit error correcting-double bit error detecting codes. One such attempt is disclosed in an article entitled: While the technique of Hsaio results in useful correction codes, the addition of the number of parity bits needed for error detection and correction by the Hsaio technique often results in too high an overhead, thereby rendering the technique of Hsaio unusable in certain applications.
A coding scheme is implemented which uses through checking parity bits appended to each byte as check bits. The remaining check bits are generated such that the combination of through checking parity bits and remaining check bits together provide single bit error correction and double bit error detection. While the scheme of White is useful, it is considerably more complex in handling certain types of double bit errors than that of the present invention. The technique of Popp used a reduced set of check bits to only handle single bit errors in order to reduce the complexity of the technique and was able to pipeline the error checking activity.
The present invention, on the other hand, is likewise of low complexity, yet adds double burst error detection. The technique of Williams et al. On the other hand, the technique of the present invention takes a different approach so as to detect certain types of burst errors with less complexity and more efficiency. As with the above-cited patents, Burns et al. The object of the present invention is to provide an error correction code that can correct the most likely error pattern namely, a single bit error, as well as detecting but not correcting the next most likely error pattern, namely, two adjacent bits in error, with fewer parity bits than any other presently used code.
In the present invention, errors are detected and corrected by the generation of specific syndromes for the error pattern. A systematic code is developed by constructing a parity check matrix which, when multiplied by a vector retrieved from a RAM and corrupted by errors, produces a product known as a syndrome which is a member of one of two mutually exclusive sets.
Each possible single bit error corresponds one to one with a member of the first set of syndromes and each two bit adjacent error corresponds non-uniquely to a member of the second separate set of syndromes. The foregoing and a better understanding of the present invention will become apparent from the following detail description of example embodiments and the claims when read in connection with the accompanying drawings, all forming a part of the disclosure of this invention.
While the foregoing and following written and illustrated disclosure focuses on disclosing example embodiments of the invention, it should be clearly understood that the same is by way of illustration and example only and the invention is not limited thereto. The spirit and scope of the present invention are limited only by the terms of the appended claims. Before beginning a detailed description of the subject invention, mention of the following is in order. When appropriate, like reference numerals and characters may be used to designate identical, corresponding, or similar components in differing drawing figures.
In addition, well-known components and elements have been omitted from the drawing figures for simplicity of illustration and discussion and so as not to obscure the invention. The present invention uses the available RAM parity bits, for example, to develop a systematic error correction code capable of single bit error correction and double burst error detection.
In one example of the application of the present invention, instructions 48 bit wide may be stored in three 18 bit wide RAM chips for a total of 54 bits of storage per RAM address. Note that the exception with regard to sequentially numbered bits stored in separate RAM chips is not significant in that the probability of occurrence of double burst errors occurring in two sequentially numbered bits stored in physically separate RAM chips is extremely low.
The code is constructed by constructing its parity check matrix H. The parity check matrix has dimensions of 6 rows by 54 columns.
A row vector c of length 54 is a valid code word if and only if:. H T is the H matrix transposed. That is, H T is the H matrix with the rows changed to columns, and the columns changed to rows. A codeword c is generated from a 48 bit information vector i using a 48 row by 54 column generator matrix G that satisfies the following equations:. If a code is systematic, that is, if all of the information bits appear unaltered and in the same order in the codeword, then G can easily be constructed from H.
The requirement for G and the relationship between G and H when they describe a binary systematic code is as follows:. Note that s depends only on e and not upon the codeword c.
If only one error occurs in a codeword, then only one bit position of e will contain a 1. Each column of H can be viewed as a 6-bit number or as an element from GF 2 6.
The syndrome is excluded since it indicates no error in the codeword. As shown in FIG. These will be the syndromes of 2-bit burst errors. The resulting matrix H is now a parity check matrix for a 54, 48 linear code Step Each of the remaining 54 columns is unique, meaning that each single bit error pattern has a unique syndrome and it is possible to correct any single error by computing the syndrome of the received word.
In addition, if the 54 columns are arranged so that the sum of any two adjacent columns is equal to one of the 9 columns syndromes deleted in step 2, then 2-bit adjacent error patterns can be detected, since they have different syndromes from those of the single error patterns Step To create the systematic code described earlier, the first 6 columns of H must form a 6 by 6 identity matrix I 6.
This implies that 5 of that columns deleted in step 2 must be , , , , and The adjacent columns Again, this is because these consecutive locations are in different RAMs and are not prone to burst error as much as adjacent locations in the same RAM. A code in accordance with the present invention successfully corrects all single bits errors and detects but does not correct all weight 2 burst errors occurring in the same RAM chip.
By construction, the code will correct all single errors and detect all weight 2 adjacent errors, except those over bits Since the first 6 columns of H form an identity matrix, the code is systematic. Decoding is performed by first computing the syndrome of the received word r.
If the syndrome is a column of H, then a single error has occurred the maximum likelihood rule and the bit of r corresponding to the column in H must be inverted to correct the received word r. The lowest bits of r are stripped off and decoding is complete. If s is one of the remaining 9 syndromes, then a multiple weight error has been detected and decoding is not performed, but rather an uncorrectable error detection is noted.
As illustrated in FIG. In step , the 54 bit word is multiplied by the parity check matrix to produce a syndrome. If so, then the single bit error is corrected in step and the process is ended in step This concludes the description of the example embodiments.
Although the present invention has been described with reference to illustrative embodiments thereof, it should be as it stood that numerous other modifications and embodiments can be devised by those skilled in the art that fall within the spirit and scope of the principles of this invention.
Year of fee payment: An error correction and detection technique provides a correction code for correcting single bit errors as well as detecting but not correcting two adjacent bits in error. A received word, which may contain errors, is multiplied by a parity check matrix to produce a syndrome corresponding to one of first and second mutually exclusive sets of syndromes if the received word contains at least one error, each single bit error in the received bit word corresponding one-to-one with a member of the first of the sets of syndromes and each two bit adjacent error corresponding non-uniquely to a member of the second of the sets of syndromes.
A syndrome containing all zeros is produced if the received word contains no errors. One bit data errors in the received word are corrected, two bit errors are reported, and no action is taken if the word contains no errors.
Field of the Invention The present invention relates to a single bit error correction, double burst error detection technique and more particularly to a single bit error correction, double burst error detection code which may be used with RAMs Random Access Memories which experience single and adjacent bit errors due to the impingement of high energy particles. Description of Related Art A microprocessor executing software from RAMs can experience single and adjacent bit errors from high energy particles.
A row vector c of length 54 is a valid code word if and only if: A codeword c is generated from a 48 bit information vector i using a 48 row by 54 column generator matrix G that satisfies the following equations: The requirement for G and the relationship between G and H when they describe a binary systematic code is as follows: If one or more errors occur, e is not zero and the following is true: Start with a 6 by 63 matrix whose columns are all possible nonzero 6-bit numbers Step What is claimed is: A single bit error correction, double burst error detection method comprising:.
The method of claim 1 , the parity check matrix comprising:. An apparatus for performing single bit error correction and double burst error detection, the apparatus comprising:. The apparatus of claim 3 , wherein the parity check matrix comprises:. A method of generating a parity check matrix for use in a single bit error correction, double burst error detection technique for a 54 bit word consisting of 48 data bits and 6 bits for error detection and correction, the method comprising:.
The method of claim 5 , further comprising forming the first six columns of the resulting matrix into a 6 by 6 identity matrix and choosing 5 of the 9 deleted columns to be , , , and The method of claim 5 , the parity check matrix comprising:.
The method of claim 7 , the parity check matrix comprising:. US USB1 en System and method for more efficiently using error correction codes to facilitate memory device testing. Method for decoding data transmitted along a data channel and an apparatus for executing the method. Pipelined error detection and correction apparatus with programmable address trap.
Check bit code circuit for simultaneous single bit error correction and burst error detection. Apparatus for detecting any single bit error, detecting any two bit error, and detecting any three or four bit error in a group of four bits for a or bit data word.
Method and apparatus for performing error detection and correction with memory devices. Method and apparatus for correcting multibyte errors having improved two-level code structure. Memory implemented error detection and correction code capable of detecting errors in fetching data from a wrong address.
Apparatus and method for data error detection and correction and address error detection in a memory system.