US5778011A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for writing and protecting against random and cluster errors in image blocks
Assignee: International Business Machines Corp
•
Filing: 1995-06-07
•
Granted: 1998-07-07
•
Expires: 2015-06-07
Abstract
Abstract A method and apparatus for encoding and detecting data which can be represented in a physical array of modules recorded on a medium. Information is encoded in "image-blocks". An image-block comprises a plurality of "sub-blocks". Sub-blocks comprise a plurality of "modules". A module is the smallest unit of information within the image-block. Discrete contiguous portions of each sub-block of an image-block taken together are encoded into an outer codeword. A plurality of these outer codewords are generated and recorded across each sub-block. A portion of the information that is to be recorded within each sub-block is encoded in a plurality of inner error detection and correction codewords, each preferably stored entirely within one corresponding sub-block. Accordingly, small scattered random errors can be corrected locally by using information entirely contained within the sub-block. If a large area within a sub-block is corrupted, the information contained in each other sub-block may be used to reconstruct the data that was recorded in the corrupted sub-block. The inner codewords are "interleaved" to provide a maximum distance between parts of the same codeword.
Inventors
- 👤 Mario Blaum
- 👤 Jehoshua Bruck
- 👤 Florian Pestoni
- 👤 Felix Gustavo Emilio Safar
- 👤 Jorge L. C. Sanz
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 16:54
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/27; H03M13/2703; H03M13/29
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
179 words
A method for encoding data in an image block having a plurality of sub-blocks, each sub-block having a plurality of modules, each module representing a unit of the data, including the steps of: encoding data in an outer error correction codeword; recording the outer error correction codeword across the plurality of sub-blocks such that at least some of the modules within at least two of the sub-blocks, taken together, represent the entire outer error correction codeword; encoding, in a first inner error correction codeword, part of the recorded outer error correction codeword; recording the first inner error correction codeword in the same sub-blocks as the part of the outer error correction codeword that is used to encode the first inner error correction codeword; encoding, in a second inner error correction codeword, part of the outer error correction codeword not encoded in the first inner error correction code; and recording the second inner error correction codeword in the same sub-blocks as the part of the outer error correction codeword that is used to encoded the second inner error correction codeword.
Claim 2
Independent Claim
179 words
A method for encoding data in an image block having a plurality of sub-blocks, each sub-block having a plurality of modules, each module representing a unit of the data, including the steps of: encoding data in an outer error correction codeword; recording the outer error correction codeword across the plurality of sub-blocks such that at least some of the modules within at least two of the sub-blocks, taken together, represent the entire outer error correction codeword; encoding, in a first inner error correction codeword, part of the recorded outer error correction codeword; recording the first inner error correction codeword in the same sub-blocks as the part of the outer error correction codeword that is used to encode the first inner error correction codeword; encoding, in a second inner error correction codeword, part of the outer error correction codeword not encoded in the first inner error correction code; and recording the second inner error correction codeword in the same sub-blocks as the part of the outer error correction codeword that is used to encoded the second inner error correction codeword.
Claim 3
Dependent Claim
63 words
The method of claim 1, further including the step of: interleaving the first and second error correction codewords such that parts of the first inner error correction codeword are spaced apart from other parts of the first inner error correction codeword, and parts of the second inner error correction codeword are spaced apart from other parts of the second inner error correction codeword.
Claim 4
Dependent Claim
18 words
The method of claim 2, wherein the parts of the first and second error correction codewords are symbols.
Claim 5
Dependent Claim
21 words
The method of claim 3, wherein the parts of the first and second error correction codewords are represented by individual modules.
Claim 6
Dependent Claim
25 words
The method of claim 1, wherein the inner error correction codeword is a Hamming codeword, and the outer error correction codeword is a Reed-Solomon codeword.
Claim 7
Independent Claim
214 words
A method for encoding data in an image block having a plurality of sub-blocks, each sub-block having a plurality of modules, each module representing a unit of the data, including the steps of: encoding, in a first outer error correction codeword, a first subset of a data file; recording the first outer error correction codeword across some of the sub-blocks, such that at least some of the modules within at least two of the sub-blocks, taken together, represent the entire first outer error correction codeword; encoding, in a next outer error correction codeword, a next subset of data; recording the next error correction codeword across the sub-blocks, such that at least some of the modules within at least two of the sub-blocks, taken together, represent the entire next outer error correction codeword; repeating the step of encoding a next subset and the step of recording a next subset for additional next subsets until the entire data file has been encoded and recorded; encoding, in a first inner error correction codeword, part of at least some of the recorded outer error correction codewords; and recording the first inner error correction codeword in the same sub-blocks as the part of the outer error correction codeword that is used to encoded the first inner error correction codeword.
Claim 8
Independent Claim
214 words
A method for encoding data in an image block having a plurality of sub-blocks, each sub-block having a plurality of modules, each module representing a unit of the data, including the steps of: encoding, in a first outer error correction codeword, a first subset of a data file; recording the first outer error correction codeword across some of the sub-blocks, such that at least some of the modules within at least two of the sub-blocks, taken together, represent the entire first outer error correction codeword; encoding, in a next outer error correction codeword, a next subset of data; recording the next error correction codeword across the sub-blocks, such that at least some of the modules within at least two of the sub-blocks, taken together, represent the entire next outer error correction codeword; repeating the step of encoding a next subset and the step of recording a next subset for additional next subsets until the entire data file has been encoded and recorded; encoding, in a first inner error correction codeword, part of at least some of the recorded outer error correction codewords; and recording the first inner error correction codeword in the same sub-blocks as the part of the outer error correction codeword that is used to encoded the first inner error correction codeword.
Claim 9
Dependent Claim
28 words
The method of claim 6, wherein the part of the outer error correction codeword recorded in any one sub-block is less than the codeword is capable of correcting.
Claim 10
Dependent Claim
15 words
The method of claim 7, wherein the entire inner codeword is recorded within one sub-block.
Claim 11
Independent Claim
270 words
A method for encoding data in an image block having a plurality of sub-blocks, each sub-block comprising a plurality of modules, each module representing a unit of the data, including the steps of: encoding, in a first outer error correction codeword, a first subset of a data file; recording the first outer error correction codeword across the sub-blocks, such that at least some of the modules within at least two of the sub-blocks, taken together, represent the entire first outer error correction codeword; encoding, in a next outer error correction codeword, a next subset of the data file; recording the next error correction codeword across the sub-blocks, such that at least some of the modules within at least some of the sub-blocks, taken together, represent the entire next outer error correction codeword; repeating the step of encoding a next subset and the step of recording a next subset for additional next subsets of the file data until all of the file data has been encoded and recorded; encoding, in a first inner error correction codeword, the parts of those outer error correction codewords recorded in a first of the sub-blocks; recording the first inner error correction codeword in the first of the sub-blocks; encoding, in a next inner error correction codeword, the parts of recorded outer error correction codewords in a next of the sub-blocks; recording the next inner error correction codeword in the next of the sub-blocks; and repeating the step of encoding in a next inner error correction codeword and the step of recording the next inner error correction codeword for each additional next one of the sub-blocks.
Claim 12
Independent Claim
270 words
A method for encoding data in an image block having a plurality of sub-blocks, each sub-block comprising a plurality of modules, each module representing a unit of the data, including the steps of: encoding, in a first outer error correction codeword, a first subset of a data file; recording the first outer error correction codeword across the sub-blocks, such that at least some of the modules within at least two of the sub-blocks, taken together, represent the entire first outer error correction codeword; encoding, in a next outer error correction codeword, a next subset of the data file; recording the next error correction codeword across the sub-blocks, such that at least some of the modules within at least some of the sub-blocks, taken together, represent the entire next outer error correction codeword; repeating the step of encoding a next subset and the step of recording a next subset for additional next subsets of the file data until all of the file data has been encoded and recorded; encoding, in a first inner error correction codeword, the parts of those outer error correction codewords recorded in a first of the sub-blocks; recording the first inner error correction codeword in the first of the sub-blocks; encoding, in a next inner error correction codeword, the parts of recorded outer error correction codewords in a next of the sub-blocks; recording the next inner error correction codeword in the next of the sub-blocks; and repeating the step of encoding in a next inner error correction codeword and the step of recording the next inner error correction codeword for each additional next one of the sub-blocks.
Claim 13
Dependent Claim
28 words
The method of claim 9, wherein the part of the outer error correction codeword recorded in any one sub-block is less than the codeword is capable of correcting.
Claim 14
Dependent Claim
15 words
The method of claim 10, wherein the entire inner codeword is recorded within one sub-block.
Claim 15
Independent Claim
267 words
A method for encoding data in an image block having a plurality of sub-blocks, each sub-block comprising a plurality of modules, each modules representing a unit of the data, including the steps of: encoding, in a first outer error correction codeword, a first subset of a data file; recording the first outer error correction codeword across the sub-blocks, such that at least some of the modules within each of the sub-blocks, taken together, represent the entire first outer error correction codeword; encoding, in a next outer error correction codeword, a next subset of the data file; recording the next error correction codeword across the sub-blocks, such that at least some of the modules within each of the sub-blocks, taken together, represent the entire next outer error correction codeword; repeating the step of encoding a next subset and the step of recording a next subset for additional next subsets of the file data until all of the file data has been encoded and recorded; encoding, in a first inner error correction codeword, the parts of those outer error correction codewords recorded in a first of the sub-blocks; recording the first inner error correction codeword in the first of the sub-blocks; encoding, in a next inner error correction codeword, the parts of recorded outer error correction codewords in a next of the sub-blocks; recording the next inner error correction codeword in the next of the sub-blocks; and repeating the step of encoding in a next inner error correction codeword and the step of recording the next inner error correction codeword for each additional next subset of the data file.
Claim 16
Independent Claim
267 words
A method for encoding data in an image block having a plurality of sub-blocks, each sub-block comprising a plurality of modules, each modules representing a unit of the data, including the steps of: encoding, in a first outer error correction codeword, a first subset of a data file; recording the first outer error correction codeword across the sub-blocks, such that at least some of the modules within each of the sub-blocks, taken together, represent the entire first outer error correction codeword; encoding, in a next outer error correction codeword, a next subset of the data file; recording the next error correction codeword across the sub-blocks, such that at least some of the modules within each of the sub-blocks, taken together, represent the entire next outer error correction codeword; repeating the step of encoding a next subset and the step of recording a next subset for additional next subsets of the file data until all of the file data has been encoded and recorded; encoding, in a first inner error correction codeword, the parts of those outer error correction codewords recorded in a first of the sub-blocks; recording the first inner error correction codeword in the first of the sub-blocks; encoding, in a next inner error correction codeword, the parts of recorded outer error correction codewords in a next of the sub-blocks; recording the next inner error correction codeword in the next of the sub-blocks; and repeating the step of encoding in a next inner error correction codeword and the step of recording the next inner error correction codeword for each additional next subset of the data file.
Claim 17
Dependent Claim
49 words
The method of claim 12, further including the step of: interleaving each inner error correction codeword such that predetermined portions of the each inner error correction codeword are spaced apart from other predetermined portions of the each inner error correction codeword belonging to the same inner error correction codeword.
Claim 18
Dependent Claim
295 words
Apparatus for encoding data in an image block having a plurality of sub-blocks, each sub-block comprising a plurality of modules, each modules representing a unit of the data, including: first encoding means for receiving a first subset of a data file and encoding, in a first outer error correction codeword, the first subset of the data file; first recording means, coupled to the first encoding means, for recording the first outer error correction codeword across the sub-blocks, such that at least some of the modules within each of the sub-blocks, taken together, represent the entire first outer error correction codeword; second encoding means, for receiving a next subset of the data file and encoding, in a next outer error correction codeword, the next subset of the data file; second recording means, coupled to the second encoding means, for recording the next error correction codeword across the sub-blocks, such that at least some of the modules within each of the sub-blocks, taken together, represent the entire next outer error correction codeword; third encoding means, coupled to the first and second encoding means, for receiving each outer error correction codeword and encoding, in a first inner error correction codeword, the parts of those outer error correction codewords recorded in a first of the sub-blocks; third recording means, coupled to the third encoding means, for recording the first inner error correction codeword in the first of the sub-blocks; fourth encoding means, coupled to the first and second encoding means, for encoding, in a next inner error correction codeword, the parts of those recorded outer error correction codewords recorded in a next of the sub-blocks; and fourth recording means, coupled to the fourth encoding means, for recording the next inner error correction codeword in the next of the sub-blocks.
Claim 19
Dependent Claim
295 words
Apparatus for encoding data in an image block having a plurality of sub-blocks, each sub-block comprising a plurality of modules, each modules representing a unit of the data, including: first encoding means for receiving a first subset of a data file and encoding, in a first outer error correction codeword, the first subset of the data file; first recording means, coupled to the first encoding means, for recording the first outer error correction codeword across the sub-blocks, such that at least some of the modules within each of the sub-blocks, taken together, represent the entire first outer error correction codeword; second encoding means, for receiving a next subset of the data file and encoding, in a next outer error correction codeword, the next subset of the data file; second recording means, coupled to the second encoding means, for recording the next error correction codeword across the sub-blocks, such that at least some of the modules within each of the sub-blocks, taken together, represent the entire next outer error correction codeword; third encoding means, coupled to the first and second encoding means, for receiving each outer error correction codeword and encoding, in a first inner error correction codeword, the parts of those outer error correction codewords recorded in a first of the sub-blocks; third recording means, coupled to the third encoding means, for recording the first inner error correction codeword in the first of the sub-blocks; fourth encoding means, coupled to the first and second encoding means, for encoding, in a next inner error correction codeword, the parts of those recorded outer error correction codewords recorded in a next of the sub-blocks; and fourth recording means, coupled to the fourth encoding means, for recording the next inner error correction codeword in the next of the sub-blocks.
References Cited (Backward Citations)
US3831143A
Cited
US4728783A
Cited
US4882732A
Cited
US4924078A
Cited
GB2218240A
Cited
US5153928A
Cited
US5140596A
Cited
US5473443A
Cited
US5543937A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-07-06 | 2002-01-05 | 2002-07-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-07-06 | 2006-01-05 | 2006-07-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-07-06 | 2010-01-05 | 2010-07-07 | $7700.00 | Window Closed / Lapsed |