Modeling error correction capability with estimation of defect parameters

• US 20070101213A1
• Filed: 10/28/2005
• Published: 05/03/2007
• Est. Priority Date: 10/28/2005
• Status: Active Grant

• Current Assignee: AirBNB Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Seger, Paul
• Granted Patent: US 7,552,376 B2
• Time in Patent Office: Days
• US Class Current: 714/712
• CPC Class Codes: G11B 20/1833 by adding special lists or symbols to the coded information G11B20/1806, G11B20/1866 take precedence
• CPC Class Codes: G11B 20/1866 by interleaving G11B20/1809 takes precedence
• CPC Class Codes: G11B 2220/90 Tape-like record carriers
• CPC Class Codes: H03M 13/01 Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
• CPC Class Codes: H04B 17/0087 using auxiliary channels or channel simulators
• CPC Class Codes: H04B 17/391 Modelling the propagation channel

Abstract

A method, system and program product accurately model the error characteristics of a communications system, such as a tape storage system. Input parameters are entered which describe defect rates and sizes, Codeword Data Structure bytes, and any interleaving factor. Bit defects from simulated defect sources are generated, defined by the starting and ending bits of each defect within a codeword. Any codewords which are defect-free are filtered out and not processed further, thereby increasing the processing speed of the model. Within the defect streams, overlapping defects are merged, redefining defect regions by starting and ending bits. Because only the definitions are processed, not the entire length of the codewords or defects, processing efficiency is further enhanced. The number of defects that occur in each codeword is determined and the probability of the occurrence of N bytes in error per processed codeword may be computed. If desired, a histogram may be generated which includes the rate at which errors occurred and subsequently used to estimate the probability of an error event. Such information may then be incorporated into the design of an error correction code for the modeled system.

Claims

1. A method for modeling the error characteristics of a communications system, comprising:

establishing a number of simulated defect streams comprising a plurality of codewords;

for each simulated defect stream;

specifying a mean defect separation; and

specifying a mean defect size;

generating a defect array for each simulated defect stream, comprising storing in the defect array the starting location and the ending location of each defect within a codeword;

concatenating the defect arrays generated from each data stream into a new defect array;

merging overlapping defects in the new defect array;

apportioning the merged defects to the codewords;

generating a histogram of the number of codewords processed having k bytes in error, where k=[0 . . . m] and m equals a predetermined maximum number; and

based upon the number and location of codeword errors and an error correction capability of an error correction code, estimating the probability of a failure in the error correction code.

2. The method of claim 1, further comprising:

generating the starting locations from observations of an exponential distribution of starting locations having a mean equal to the specified mean defect separation; and

generating the stopping locations from observations of an exponential distribution of starting locations having a mean equal to the specified mean defect size.

3. The method of claim 1, further comprising processing a next codeword if a codeword contains no defects.

4. The method of claim 1, wherein merging overlapping defects comprises executing a logical OR on the defects in the new defect array.

5. The method of claim 1, wherein merging overlapping defects comprises:

sorting the new defect array by ascending starting bits;

converting the defect starting and stopping bits to corresponding byte locations; and

coalescing the resulting defect bytes.

6. The method of claim 1, wherein, if the codeword structure includes interleaved even and odd codewords, apportioning the defects comprises:

summing the number of bytes in which defects start, continue or stop in an even codeword to determine the number of bytes in error in the even codeword; and

summing the number of bytes in which defects start, continue or stop in an odd codeword to determine the number of bytes in error in the odd codeword.

7. The system of claim 1, further calculating the probability of the occurrence of N bytes in error per processed codeword.

8. A system for modeling the error characteristics of a communications system, comprising:

an input configured to receive defect parameters, including;

an interleave number for interleaving simulated codewords;

a value identifying a number of a plurality of simulated defect streams from respective simulated defect sources; and

for each simulated defect stream, a mean defect separation in bits and a mean defect size in bits;

a codeword generator configured to generate a stream of simulated codewords;

a codeword interleaver configured to interleave the simulated codewords according to the input interleave number and to output a stream of codeword data structures;

a defect generator configured to inject simulated defects into the codeword data structure stream according to the input parameters and to output the simulated defect streams;

a combined defect array having an entry for each defect in each simulated defect stream, each entry comprising a starting location and an ending location of the defect;

a merge module configured to coalesce overlapping simulated defects; and

a defect processor configured to determine the number of bytes in error in each codeword data structure.

9. The system of claim 8, further comprising a histogram generator coupled to the defect processor and configured to output a visual indication of the number of bytes in error in each codeword data structure.

10. The system of claim 8, further comprising a filter associated with each simulated defect stream and configured to pass only codeword data structures in the simulated defect streams having at least one defective bit.

11. The system of claim 8, wherein the merge module comprises:

a sorter configured to sort the entries in the combined defect array based upon the starting location of each defect; and

a coalescer configured to merge overlapping defects into a single defect based upon the starting and ending locations of each defect.

12. The system of claim 8, further comprising a probability calculator configured to calculate the probability of the occurrence of N bytes in error per processed codeword.

13. A computer program product of a computer readable medium usable with a programmable computer, the computer program product having computer-readable code embodied therein for modeling the error characteristics of a communications system, the computer-readable code comprising instructions for:

establishing a number of simulated defect streams comprising a plurality of codewords;

for each simulated defect stream;

specifying a mean defect separation; and

specifying a mean defect size;

generating a defect array for each simulated defect stream, comprising storing in the defect array the starting location and the ending location of each defect within a codeword;

concatenating the defect arrays generated from each data stream into a new defect array;

merging overlapping defects in the new defect array;

apportioning the merged defects to the codewords;

generating a histogram of the number of codewords processed having k bytes in error, where k=[0 . . . m] and m equals a predetermined maximum number; and

based upon the number and location of codeword errors and an error correction capability of an error correction code, estimating the probability of a failure in the error correction code.

14. The computer program product of claim 13, the computer-readable code further comprising instructions for:

generating the starting locations from observations of an exponential distribution of starting locations having a mean equal to the specified mean defect separation; and

generating the stopping locations from observations of an exponential distribution of starting locations having a mean equal to the specified mean defect size.

15. The computer program product of claim 13, the computer-readable code further comprising instructions for processing a next codeword if a codeword contains no defects.

16. The computer program product of claim 13, wherein the instructions for merging overlapping defects comprise instructions for executing a logical OR on the defects in the new defect array.

17. The computer program product of claim 13, wherein the instructions for merging overlapping defects comprise instructions for:

sorting the new defect array by ascending starting bits;

converting the defect starting and stopping bits into corresponding byte locations; and

coalescing the resulting defect bytes.

18. The computer program product of claim 13, wherein, if the codeword structure includes interleaved even and odd codewords, the instructions for apportioning the defects comprise instructions for:

summing the number of bytes in which defects start, continue or stop in an even codeword to determine the number of bytes in error in the even codeword; and

summing the number of bytes in which defects start, continue or stop in an odd codeword to determine the number of bytes in error in the odd codeword.

19. The computer program product of claim 13, the computer-readable code further comprising instructions for calculating the probability of the occurrence of N bytes in error per processed codeword.

20. A method for designing an error correction code for a communications system, comprising:

a) defining a simulated codeword data structure;

b) defining one or more simulated defect streams, each simulated defect stream representing a simulated defect source;

c) generating a set of defects having zero or more simulated defects from each of the simulated defect streams, each defect being defined by a starting location and an ending location within the simulated codeword data structure;

d) if zero defects are generated for all of the simulated defect streams, repeating step c) for a next set of defects;

e) merging the starting and stopping locations of the simulated defects in the set of defects;

f) determining the number and locations of merged simulated defects;

g) repeating steps c) through f) a plurality of iterations, each iteration representing one codeword processed;

h) determining the probability of occurrence of N-bytes in error per codeword processed; and

i) designing an error correction code to correct errors in a data stream up to and including N-bytes in error per codeword in the data stream.

21. The method of claim 20, wherein defining one or more simulated defect streams comprises:

establishing a mean defect separation for simulated defects in each simulated defect stream; and

establishing a mean defect size for simulated defects in each simulated defect stream.

22. The method of claim 21, wherein:

defining a starting location of a simulated defect comprises applying an observed exponential distribution of start locations having a mean equal to the established mean defect separation; and

defining a stopping location of a simulated defect comprises applying an observed exponential distribution of start locations having a mean equal to the established mean defect size.

23. The method of claim 20, wherein merging comprises:

aggregating overlapping defects;

subsuming contained defects; and

truncating defects which extend beyond boundaries of the codeword data structure.

24. The method of claim 20, wherein defining a simulated codeword data structure comprises establishing a codeword interleave factor whereby a codeword data structure comprises at least two interleaved codewords.

25. The method of claim 24, further comprising apportioning the merged simulated defects to the codewords interleaved in the codeword data structure.

26. A system for designing an error correction code for a communications system, comprising:

means for defining a simulated codeword data structure;

means for defining one or more simulated defect streams, each simulated defect stream representing a simulated defect source;

means for generating a set of defects having zero or more simulated defects from each of the simulated defect streams, each defect being defined by a starting location and an ending location within the simulated codeword data structure;

means for returning processing to the means for generating to generate a next set of defects if zero defects are generated for all of the simulated defect streams;

means for merging the starting and stopping locations of the simulated defects in the set of defects;

means for determining the number and locations of merged simulated defects;

means for returning process to the means for generating over a plurality of iterations, each iteration representing one codeword processed;

means for determining the probability of occurrence of N-bytes in error per codeword processed; and

means for designing an error correction code to correct errors in a data stream up to and including N-bytes in error per codeword in the data stream.

27. The system of claim 26, wherein the means for defining one or more simulated defect streams comprises:

means for receiving an input establishing a mean defect separation for simulated defects in each simulated defect stream; and

means for receiving an input establishing a mean defect size for simulated defects in each simulated defect stream.

28. The system of claim 27, wherein:

the means for defining a starting location of a simulated defect comprises means for applying an observed exponential distribution of start locations having a mean equal to the established mean defect separation; and

the means for defining a stopping location of a simulated defect comprises means for applying an observed exponential distribution of start locations having a mean equal to the established mean defect size.

29. The system of claim 26, wherein the means for merging comprises:

means for aggregating overlapping defects;

means for subsuming contained defects; and

means for truncating defects which extend beyond boundaries of the codeword data structure.

30. The system of claim 26, wherein the means for defining a simulated codeword data structure comprises means for receiving an input establishing a codeword interleave factor whereby a codeword data structure comprises at least two interleaved codewords.

31. The system of claim 30, further comprising means for apportioning the merged simulated defects to the codewords interleaved in the codeword data structure.