Granted Patent B1

US 6,842,873 · App. 10/057,774 · Granted Jan 11, 2005

Abstract

Claims (166)

1. A method for correcting errors introduced into a set of data bits during transmission of the set of data bits over a channel, comprising:

determining a confidence measure for each data bit based only on the values of one or more of the data bits, each confidence measure representing the probability that the value of the corresponding data bit is correct; and

changing the value of a given data bit when the confidence measure for the given data bit indicates that the value of the given data bit is not correct, thereby producing a corrected data bit.

2. The method of claim 1 , further comprising:

determining a second confidence measure for each corrected data bit based on the confidence measure for the data bit corresponding to that corrected data bit and the values of one or more of the corrected data bits, each second confidence measure representing the probability that the value of the corresponding corrected data bit is correct; and

changing the value of a given corrected data bit when the second confidence measure for the given corrected data bit indicates that the value of the given corrected data bit is not correct, thereby producing twice-corrected data bits.

3. The method of claim 2 , wherein determining a second confidence measure for each corrected data bit comprises:

generating a plurality of second check bits based on the corrected data bits such that each of the second check bits is a predetermined function of one or more bits of the corrected data; and

determining the second confidence measures based on the values of the second check bits and the confidence measures.

4. The method of claim 1 , wherein determining a confidence measure for each data bit comprises:

generating a plurality of check bits based on the data bits such that each of the check bits is a predetermined function of one or more of the data bits; and

determining the confidence measures based on the values of the check bits.

5. The method of claim 4 , wherein generating comprises:

taking the logical exclusive-or of a predetermined subset of the data bits, thereby producing a predetermined one of the check bits.

6. The method of claim 1 , further comprising:

determining a composite confidence measure based on the confidence measures; and

executing the changing step only when the composite confidence measure falls below a predetermined composite confidence threshold.

7. The method of claim 1 , wherein the data bits are encoded before transmission over the channel using a majority-logic-decodable code.

8. The method of claim 1 , wherein the channel is a fiber-optic channel.

9. The method of claim 1 , wherein the channel is an optical storage medium.

10. The method of claim 9 , wherein the optical storage medium is a digital video disc (DVD).

11. The method of claim 9 , wherein the optical storage medium is a compact disc (CD).

12. A method for correcting errors introduced into a set of data bits during transmission of the set of data bits over a channel, comprising:

determining a confidence measure for each data bit based on the received energy level of that data bit, each confidence measure representing the probability that the value of the corresponding data bit has a predetermined value;

selecting a value for each data bit based on the corresponding confidence measure, thereby producing corrected data bits;

determining a second confidence measure for each corrected data bit based on the confidence measure for the data bit corresponding to that corrected data bit and the values of one or more of the corrected data bits, each second confidence measure representing the probability that the value of the corresponding corrected data bit is correct; and

changing the value of a given corrected data bit when the second confidence measure for the given corrected data bit indicates that the value of the given corrected data bit is not correct, thereby producing twice-corrected data bits.

13. The method of claim 12 , wherein determining a confidence measure for each data bit comprises:

generating a plurality of check bits based on the data bits such that each of the check bits is a predetermined function of one or more of the data bits; and

determining the confidence measures based on the values of the check bits.

14. The method of claim 13 , wherein generating comprises:

taking the logical exclusive-or of a predetermined subset of the data bits, thereby producing a predetermined one of the check bits.

15. The method of claim 12 , wherein determining a second confidence measure for each corrected data bit comprises:

generating a plurality of second check bits based on the corrected data bits such that each of the second check bits is a predetermined function of one or more bits of the corrected data; and

determining the second confidence measures based on the values of the second check bits and the confidence measures.

16. The method of claim 12 , further comprising:

determining a composite confidence measure based on the confidence measures; and

executing the changing step only when the composite confidence measure falls below a predetermined composite confidence threshold.

17. The method of claim 12 , wherein the channel is a fiber-optic channel.

18. The method of claim 12 , wherein the channel is an optical storage medium.

19. The method of claim 18 , wherein the optical storage medium is a digital video disc (DVD).

20. The method of claim 18 , wherein the optical storage medium is a compact disc (CD).

21. Computer-readable media embodying instructions executable by a computer to perform a method for correcting errors introduced into a set of data bits during transmission of the set of data bits over a channel, the method comprising:

determining a confidence measure for each data bit based only on the values of one or more of the data bits, each confidence measure representing the probability that the value of the corresponding data bit is correct; and

changing the value of a given data bit when the confidence measure for the given data bit indicates that the value of the given data bit is not correct, thereby producing a corrected data bit.

22. The media of claim 21 , wherein the method further comprises:

determining a second confidence measure for each corrected data bit based on the confidence measure for the data bit corresponding to that corrected data bit and the values of one or more of the corrected data bits, each second confidence measure representing the probability that the value of the corresponding corrected data bit is correct; and

changing the value of a given corrected data bit when the second confidence measure for the given corrected data bit indicates that the value of the given corrected data bit is not correct, thereby producing twice-corrected data bits.

23. The media of claim 22 , wherein determining a second confidence measure for each corrected data bit comprises:

generating a plurality of second check bits based on the corrected data bits such that each of the second check bits is a predetermined function of one or more bits of the corrected data; and

determining the second confidence measures based on the values of the second check bits and the confidence measures.

24. The media of claim 21 , wherein determining a confidence measure for each data bit comprises:

generating a plurality of check bits based on the data bits such that each of the check bits is a predetermined function of one or more of the data bits; and

determining the confidence measures based on the values of the check bits.

25. The media of claim 24 , wherein generating comprises:

taking the logical exclusive-or of a predetermined subset of the data bits, thereby producing a predetermined one of the check bits.

26. The media of claim 21 , wherein the method further comprises:

determining a composite confidence measure based on the confidence measures; and

executing the changing step only when the composite confidence measure falls below a predetermined composite confidence threshold.

27. The media of claim 21 , wherein the data bits are encoded before transmission over the channel using a majority-logic-decodable code.

28. The media of claim 21 , wherein the channel is a fiber-optic channel.

29. The media of claim 21 , wherein the channel is an optical storage medium.

30. The media of claim 29 , wherein the optical storage device medium is a digital video disc (DVD).

31. The media of claim 29 , wherein the optical storage device medium is a compact disc (CD).

32. Computer-readable media embodying instructions executable by a computer to perform a method for correcting errors introduced into a set of data bits during transmission of the set of data bits over a channel, the method comprising:

determining a confidence measure for each data bit based on the received energy level of that data bit, each confidence measure representing the probability that the value of the corresponding data bit has a predetermined value;

selecting a value for each data bit based on the corresponding confidence measure, thereby producing corrected data bits;

determining a second confidence measure for each corrected data bit based on the confidence measure for the data bit corresponding to that corrected data bit and the values of one or more of the corrected data bits, each second confidence measure representing the probability that the value of the corresponding corrected data bit is correct; and

changing the value of a given corrected data bit when the second confidence measure for the given corrected data bit indicates that the value of the given corrected data bit is not correct, thereby producing twice-corrected data bits.

33. The media of claim 32 , wherein determining a confidence measure for each data bit comprises:

generating a plurality of check bits based on the data bits such that each of the check bits is a predetermined function of one or more of the data bits; and

determining the confidence measures based on the values of the check bits.

34. The media of claim 33 , wherein generating comprises:

taking the logical exclusive-or of a predetermined subset of the data bits, thereby producing a predetermined one of the check bits.

35. The media of claim 32 , wherein determining a second confidence measure for each corrected data bit comprises:

generating a plurality of second check bits based on the corrected data bits such that each of the second check bits is a predetermined function of one or more bits of the corrected data; and

determining the second confidence measures based on the values of the second check bits and the confidence measures.

36. The media of claim 32 , wherein the method further comprises:

determining a composite confidence measure based on the confidence measures; and

executing the changing step only when the composite confidence measure falls below a predetermined composite confidence threshold.

37. The media of claim 32 , wherein the channel is a fiber-optic channel.

38. The media of claim 32 , wherein the channel is an optical storage medium.

39. The media of claim 38 , wherein the optical storage device medium is a digital video disc (DVD).

40. The media of claim 38 , wherein the optical storage device medium is a compact disc (CD).

41. An apparatus for correcting errors introduced into a set of data bits during transmission of the set of data bits over a channel, comprising:

means for determining a confidence measure for each data bit based only on the values of one or more of the data bits, each confidence measure representing the probability that the value of the corresponding data bit is correct; and

means for changing the value of a given data bit when the confidence measure for the given data bit indicates that the value of the given data bit is not correct, thereby producing a corrected data bit.

42. The apparatus of claim 41 , further comprising:

means for determining a second confidence measure for each corrected data bit based on the confidence measure for the data bit corresponding to that corrected data bit and the values of one or more of the corrected data bits, each second confidence measure representing the probability that the value of the corresponding corrected data bit is correct; and

means for changing the value of a given corrected data bit when the second confidence measure for the given corrected data bit indicates that the value of the given corrected data bit is not correct, thereby producing twice-corrected data bits.

43. The apparatus of claim 42 , wherein means for determining a second confidence measure for each corrected data bit comprises:

means for generating a plurality of second check bits based on the corrected data bits such that each of the second check bits is a predetermined function of one or more bits of the corrected data; and

means for determining the second confidence measures based on the values of the second check bits and the confidence measures.

44. The apparatus of claim 41 , wherein means for determining a confidence measure for each data bit comprises:

means for generating a plurality of check bits based on the data bits such that each of the check bits is a predetermined function of one or more of the data bits; and

means for determining the confidence measures based on the values of the check bits.

45. The apparatus of claim 44 , wherein means for generating comprises:

means for taking the logical exclusive-or of a predetermined subset of the data bits, thereby producing a predetermined one of the check bits.

46. The apparatus of claim 41 , further comprising:

means for determining a composite confidence measure based on the confidence measures; and

means for executing the changing step only when the composite confidence measure falls below a predetermined composite confidence threshold.

47. The apparatus of claim 41 , wherein the data bits are encoded before transmission over the channel using a majority-logic-decodable code.

48. The apparatus of claim 41 , wherein the channel is a fiber-optic channel.

49. The apparatus of claim 41 , wherein the channel is an optical storage medium.

50. The apparatus of claim 49 , where in the optical storage device medium is a digital video disc (DVD).

51. The apparatus of claim 49 , wherein the optical storage device medium is a compact disc (CD).

52. An apparatus for correcting errors introduced into a set of data bits during transmission of the set of data bits over a channel, comprising:

means for determining a confidence measure for each data bit based on the received energy level of that data bit, each confidence measure representing the probability that the value of the corresponding data bit has a predetermined value;

means for selecting a value for each data bit based on the corresponding confidence measure, thereby producing corrected data bits;

means for determining a second confidence measure for each corrected data bit based on the confidence measure for the data bit corresponding to that corrected data bit and the values of one or more of the corrected data bits, each second confidence measure representing the probability that the value of the corresponding corrected data bit is correct; and

means for changing the value of a given corrected data bit when the second confidence measure for the given corrected data bit indicates that the value of the given corrected data bit is not correct, thereby producing twice-corrected data bits.

53. The apparatus of claim 52 , wherein means for determining a confidence measure for each data bit comprises:

means for generating a plurality of check bits based on the data bits such that each of the check bits is a predetermined function of one or more of the data bits; and

means for determining the confidence measures based on the values of the check bits.

54. The apparatus of claim 53 , wherein means for generating comprises:

means for taking the logical exclusive-or of a predetermined subset of the data bits, thereby producing a predetermined one of the check bits.

55. The apparatus of claim 52 , wherein means for determining a second confidence measure for each corrected data bit comprises:

means for generating a plurality of second check bits based on the corrected data bits such that each of the second check bits is a predetermined function of one or more bits of the corrected data; and

means for determining the second confidence measures based on the values of the second check bits and the confidence measures.

56. The apparatus of claim 52 , further comprising:

means for determining a composite confidence measure based on the confidence measures; and

means for executing the changing step only when the composite confidence measure falls below a predetermined composite confidence threshold.

57. The apparatus of claim 52 , wherein the channel is a fiber-optic channel.

58. The apparatus of claim 52 , wherein the channel is an optical storage medium.

59. The apparatus of claim 58 , wherein the optical storage device medium is a compact disc (CD).

60. The apparatus of claim 58 , wherein the optical storage device medium is a digital video disc (DVD).

61. An apparatus for correcting errors introduced into a set of data bits during transmission of the set of data bits over a channel, comprising:

a checker to determine a confidence measure for each data bit based only on the values of one or more of the data bits, each confidence measure representing the probability that the value of the corresponding data bit is correct; and

a corrector to change the value of a given data bit when the confidence measure for the given data bit indicates that the value of the given data bit is not correct, thereby producing a corrected data bit.

62. The apparatus of claim 61 , further comprising:

a second checker to determine a second confidence measure for each corrected data bit based on the confidence measure for the data bit corresponding to that corrected data bit and the values of one or more of the corrected data bits, each second confidence measure representing the probability that the value of the corresponding corrected data bit is correct; and

a second corrector to change the value of a given corrected data bit when the second confidence measure for the given corrected data bit indicates that the value of the given corrected data bit is not correct, thereby producing twice-corrected data bits.

63. The apparatus of claim 62 , wherein the second checker:

generates a plurality of second check bits based on the corrected data bits such that each of the second check bits is a predetermined function of one or more bits of the corrected data; and

determines the second confidence measures based on the values of the second check bits and the confidence measures.

64. The apparatus of claim 61 , wherein the checker:

generates a plurality of check bits based on the data bits such that each of the check bits is a predetermined function of one or more of the data bits; and

determines the confidence measures based on the values of the check bits.

65. The apparatus of claim 64 , wherein the checker further takes the logical exclusive-or of a predetermined subset of the data bits, thereby producing a predetermined one of the check bits.

66. The apparatus of claim 61 , wherein the corrector:

determines a composite confidence measure based on the confidence measures; and

changes the value of a given data bit only when the composite confidence measure falls below a predetermined composite confidence threshold.

67. The apparatus of claim 61 , wherein the data bits are encoded before transmission over the channel using a majority-logic-decodable code.

68. The apparatus of claim 61 , wherein the channel is a fiber-optic channel.

69. The apparatus of claim 61 , wherein the channel is an optical storage medium.

70. The apparatus of claim 69 , wherein the optical storage device medium is a digital video disc (DVD).

71. The apparatus of claim 69 , wherein the optical storage device medium is a compact disc (CD).

72. An apparatus for correcting errors introduced into a set of data bits during transmission of the set of data bits over a channel comprising:

a first checker to determine a confidence measure for each data bit based on the received energy level of that data bit, each confidence measure representing the probability that the value of the corresponding data bit has a predetermined value;

a first corrector to select a value for each data bit based on the corresponding confidence measure, thereby producing corrected data bits;

a second checker to determine a second confidence measure for each corrected data bit based on the confidence measure for the data bit corresponding to that corrected data bit and the values of one or more of the corrected data bits, each second confidence measure representing the probability that the value of the corresponding corrected data bit is correct; and

a second corrector to change the value of a given corrected data bit when the second confidence measure for the given corrected data bit indicates that the value of the given corrected data bit is not correct, thereby producing twice-corrected data bits.

73. The apparatus of claim 72 , wherein the first checker:

generates a plurality of check bits based on the data bits such that each of the check bits is a predetermined function of one or more of the data bits; and

determines the confidence measures based on the values of the check bits.

74. The apparatus of claim 73 , wherein the first checker further takes the logical exclusive-or of a predetermined subset of the data bits, thereby producing a predetermined one of the check bits.

75. The apparatus of claim 72 , wherein the second checker:

generates a plurality of second check bits based on the corrected data bits such that each of the second check bits is a predetermined function of one or more bits of the corrected data; and

determines the second confidence measures based on the values of the second check bits and the confidence measures.

76. The apparatus of claim 72 , wherein the first corrector:

determines a composite confidence measure based on the confidence measures; and

changes the value of a given data bit only when the composite confidence measure falls below a predetermined composite confidence threshold.

77. The apparatus of claim 72 , wherein the channel is a fiber-optic channel.

78. The apparatus of claim 72 , wherein the channel is an optical storage medium.

79. The apparatus of claim 78 , wherein the optical storage device medium is a digital video disc (DVD).

80. The apparatus of claim 78 , wherein the optical storage device medium is a compact disc (CD).

Assignments (6)