Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-03-26
2002-10-22
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S776000
Reexamination Certificate
active
06470469
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to the field of computer data recovery transformations, and in particular to recovery of signal data such as image data, wherein portions of the data have been lost.
COPYRIGHT NOTICE/PERMISSION
A portion of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever. The following notice applies to the software and data as described below and in the drawing hereto: Copyright© 1998-1999, Microsoft Corporation. All Rights Reserved.
BACKGROUND
Channels used to transmit data are sometimes “noisy” and can corrupt or lose portions of the data transmitted. A channel is said to “corrupt” portions of the data if it changes some data values during transmission without notice to the receiver. A channel is said to “lose” or “erase” portions of the data if it does not transmit some data values to the receiver, but notifies the receiver as to which data items were not transmitted. Accordingly, channels may be classified as “corruption” or “erasure” channels. An example of a corruption channel is a wireless communications system wherein data are occasionally corrupted due to electromagnetic noise in the atmosphere. Another example of a corruption channel is a storage system such as a magnetic disk, a Compact Disk Read-Only Memory (“CDROM”), or a Digital Versatile Disk (“DVD”), wherein data are occasionally corrupted due to scratches and dust on the recording media or due to writing or reading errors in the channels which move data onto or off from the media. An example of an erasure channel is a packet communications network wherein certain packets are lost in transmission, and wherein the receiver can detect which data are lost using packet sequence numbers and/or other means. Another example of an erasure channel is a storage system wherein the data are striped across a number of disks, any of which can fail at random, and whose failure can be detected, such that which data items are missing is known. Any corruption channel can appear, at a high level, to be an erasure channel, by appropriate low-level error detection processing. For example, a parity check or checksum word can be transmitted along with a block of data; if the received checksum does not agree with the received data, then an error is detected in the block of data, and the block of data can be considered erased by the channel. It is desirable to have ways to recover the data that is corrupted or lost. For example, image data that have either pixels or blocks that have been lost would have blank (perhaps white or black on a display monitor) or would appear to have “noise” or snow in the received images. A “pixel” is an individual picture element, and is generally represented by a single value indicating, for example, the intensity of image at a point, or the intensity of each of three colors. A “block” is a group of adjacent pixels, generally a rectangle. For example, a block could be a 16-by-16-pixel portion of a larger image.
A “channel” can be a transmission channel, such as digital television broadcast or cable television transmission, or a telephony packet network that moves data over a distance or space. A “channel” can also be a storage channel that stores the data on a storage medium and then reads the data at a later time.
Error-correction codes have been devised for both corruption and erasure channels, and are well known. (See S. Lin and D. J. Costello,
Error Control Coding: Fundamentals and Applications
, Prentice-Hall, 1983, herein Lin and Costello.) By far, the most common error-correction codes are based on linear transformations of the data to add redundancy. If x is a data vector with K elements, and F is an N×K matrix, with N≧K, then y=Fx is a vector with N elements. N−K of these elements can be considered redundant information. By transmitting the code vector y instead of x, the receiver can recover x even if some elements of y are corrupted or lost. In particular, if y is transmitted through an erasure channel, and no more than N−K elements of y are erased, then x can be recovered perfectly. For example, if x is a vector containing 3 binary elements, and
F
=
[
1
0
0
0
1
0
0
0
1
1
1
1
]
,
then y is a vector containing 4 binary elements, the first three of which are equal to x (this is called the “systematic” part of y) and the last of which is equal to the sum of the bits in x, modulo 2. That is, the last bit of y is equal to the exclusive-OR, or parity, of x. If any three bits of y are recovered, then x can be recovered perfectly. On the other hand, if two or more bits of y are erased, then x cannot be recovered perfectly; the bits of x that are lost are unrecoverable in this case.
Error-correction codes are intended to recover symbolic data. In the example above, the elements of x are binary symbols. In general, they can be members of a finite field, e.g., they can be M-ary symbols. There is no notion of distance between members of a finite field, except the so-called discrete topology: two elements may be equal or not equal. There is no notion of approximation. Hence in error-correction coding, there is no notion of approximate recovery. An element of x is either recoverable, or it is not.
One type of data for which approximation is useful is signal data, such as image, video, or audio data. Signal data, in contrast to symbol data, has elements that are members of an infinite field, such as the rational numbers, the real numbers, or the complex numbers. In a digital computer, these elements must be represented by finite precision numbers, such as 16-bit signed integers or 32-bit floating-point numbers. However there is a natural notion of distance between two such elements, e.g., the absolute value of their difference. As a consequence, any data vector x containing signal data (such as an image or a frame of audio) can be approximated by another data vector {circumflex over (x)}, where the degree of approximation can be measured by the Euclidean distance, a perceptual metric, or some other measure.
It is possible to apply error-correction codes to the transmission of signal data over erasure channels, by treating each signal element as a discrete M-ary symbol. However, this is inefficient. Signals need not be transmitted exactly, provided the approximation error between the signal and its reconstruction is small, on average. Applying a high-redundancy error-correction code can ensure this, but such a solution is expensive in terms of transmission capacity. An alternative is to use “unequal error protection,” which is a technique in which only the most important parts of the signal are protected with high redundancy. The less important parts are protected with low redundancy or not at all. One way to implement unequal error protection is the following. If the signal vector x contains elements that are 16-bit integers, then x can be stratified into 16 “bit-planes”. Then each bit-plane can be protected using a binary error-correction code with a redundancy commensurate with the importance of the bit-plane in approximating the signal vector x. (See for example J. Hagenauer, “Rate-Compatible Punctured Convolutional Codes (RCPC Codes) and their Applications,” IEEE Trans. on Communications, April 1988; A. Albanese, J. Blömer, J. Edmonds, M. Luby, and M. Sudan, “Priority Encoding Transmission,” IEEE Trans. Information Theory, November 1996; G. Davis and J. Danskin, “Joint Source and Channel Coding for Image Transmission Over Lossy Packet Networks,” SPIE Conf. on Wavelet Applic. of Digital Image Processing, August 1996.)
Even with the technique of unequal error protection, error-correction codes may not be ideally suited to protection of signal data. Ideally, all of the received bits should be used to improve the approximation of the reconstr
Chou Philip A.
Mehrotra Sanjeev
Wang Albert S.
Baker Stephen M.
Lyon Katrina A.
Lyon & Harr LLP
Microsoft Corp.
LandOfFree
Reconstruction of missing coefficients of overcomplete... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Reconstruction of missing coefficients of overcomplete..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reconstruction of missing coefficients of overcomplete... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2948585