Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-02-12
2001-12-04
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
Reexamination Certificate
active
06327691
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to improvements in digital audio processing, and relates specifically to a system and method for computing and encoding an error detection sequence in digital audio encoding.
2. Description of the Background Art
Digital audio is now in widespread use in digital video disk (DVD) players, digital satellite systems (DSS), and digital television (DTV). Each of these systems has incorporated digital audio compression in order to fit more digital audio in a storage device of limited storage capacity, or to transmit digital audio over a channel of limited bandwidth. As part of the digital audio compression method used, steps must be taken to ensure against errors in the transmission of the data. The transmission may take many forms, including encoding and writing data to a disk and subsequently reading and decoding data from it, or direct radio-frequency broadcast from a encoder and transmitter to a receiver and decoder. In most cases, additional bits may be added by the transmitter (and encoder) to the digital audio data so that the receiver (and decoder) can evaluate the received data for the presence or absence of errors.
A frame check sequence (FCS) is a number which, when appended to a transmitted message, allows the receiver to deduce the presence or absence of errors in transmission. The cyclic redundancy check (CRC) method considers the individual frames of data in a serial bitstream between a transmitter and a receiver to be large binary numbers. The transmitter in the CRC method divides each number by a fixed constant, and then examines the remainders. In the most common practice, these remainders, one example of an FCS, are appended to the end (i.e. the part arriving last in time) of the numbers. These appended numbers are then transmitted to the receiver. The receiver then divides the appended numbers by the same fixed constant previously used by the transmitter. If the new remainders of these divisions are 0, then the receiver may deduce that it received the frames in the serial bitstream without errors.
Because binary division consists primarily of logical shifting of the data bits, a CRC FCS is commonly generated and evaluated using some form of hardware shift-register employing feedback. An advantage of many CRC embodiments which append the FCS at the end of the bitstream is that the same circuit design may be used to both generate the FCS in the transmitter and evaluate the FCS in the receiver. The FCS is generated by shifting the bitstream through the shift-register. The number remaining within the shift-register after the last bit of the bitstream has been shifted into the shift-register is used as the FCS. When this FCS is appended to the end of the bitstream, an identical shift-register in the receiver may be used to evaluate the incoming appended bitstream. After shifting the entire appended bitstream through the receiver's shift-register, if there are no errors from transmission the shift-register should contain binary 0.
One example of a transmitter sending data to a receiver is the digital audio compression method first used by Dolby® Labs. The Advanced Television Systems Committee (ATSC) selected this Dolby® Labs design for use in the digital television (DTV) system (formerly known as high-definition television, or HDTV). This design is set forth in the Audio Compression version 3 (AC-3) specification, document number ATSC A/52 (here after “the AC-3 specification”), which is hereby incorporated by reference. The AC-3 specification has been subsequently selected for Region 1 (North American market) DVD's and selected DSS broadcasts.
The AC-3 specification presents a standard decoder design for digital audio, which allows all AC-3 encoded digital audio recordings to be reproduced by differing vendors' equipment. Certain parts of the encoder design must also be standard in order that the resulting encoded digital audio may be reproduced with the standard decoder design. However, many of the design details in areas, such as the calculation and encoding of one of two cyclic redundancy check (CRC) frame check sequences (FCS), may be left to the individual designer with the requirement that the design does not affect the ability of the resulting encoded digital audio to be reproduced with the standard decoder design.
It is less common to append a FCS at the beginning (i.e. the part arriving first in time), rather than at the end, of a bitstream. However, the AC-3 specification provides for both an appended-at-the-beginning FCS, called CRC1, as well as an appended-at-the-end FCS, called CRC2. Furthermore, the AC-3 specification requires that no matter how CRC1 is generated it must be capable of evaluation using the same shift-register in the decoder as CRC2. No system or method capable of generating CRC1 is disclosed in the AC-3 specification.
Therefore, techniques for generating an appended-at-the-beginning CRC1 which may be evaluated by a standard appended-at-the-end shift-register remains a significant consideration in digital audio operations.
SUMMARY OF THE INVENTION
The present invention includes a system and method for calculating a cyclic redundancy check (CRC) frame check sequence (FCS) which may be appended at the beginning of a frame of digital data in a bitstream and yet be evaluated utilizing the same circuitry that is used to evaluate another CRC FCS appended at the end of the frame. In one embodiment where the bitstream is used for AC-3 digital audio, a special shift register including feedback may be used to calculate a value for the appended-at-the-beginning CRC FCS, referred to as CRC1. When that value for CRC1 is appended at the front of the first ⅝ of a frame of digital data, the appended partial frame may be correctly evaluated for the presence or absence of errors using the evaluation circuitry in a standard AC-3 decoder.
An AC-3 decoder evaluates the frames of digital data in a bitstream for errors by treating each frame as a single binary number, with the bit transmitted first-in-time treated as the most-significant bit (MSB) of the large binary number. This treatment is referred to herein as the forward representation. The AC-3 decoder performs this procedure by dividing the previously-appended binary number by an evaluation constant divisor, and then checking to see if the remainder is 0. In one embodiment of the present invention, the evaluation constant divisor is 11000000000000101 binary (98,309 decimal). Because working with large binary numbers may be cumbersome, a method known as polynomial representation is often used. For example, the above evaluation constant divisor may be represented as x
16
+x
15
+x
2
+1. The variable x in this polynomial is referred to as a dummy variable because it serves as a placeholder for the exponent. In the polynomial representation, the constant divisor is called a generating polynomial.
The present invention may be used to determine that number which, when appended at the front of a frame of digital data in a digital bitstream, will give a 0 remainder when the appended frame is divided by the generating polynomial x
16
+x
15
+x
2
+1. In the present invention, a second alternate treatment of the frame is used in which the bit transmitted last-in-time is treated as the MSB of a large binary number. This treatment is referred to as the backwards representation. A new dummy variable y is introduced to represent divisors when dividing this backwards representation number to extract remainders. When a backwards representation number is divided by a generating constant divisor represented by the generating polynomial y
16
+y
14
+y
1
+1 (i.e. 10100000000000011 binary), the resulting remainder may serve as the desired value of CRC1.
One embodiment of the present invention includes an apparatus which may be used to divide a backwards representation number by the generating polynomial y
16
+y
14
+y
1
+1. In this embodiment, a linear feedback shif
Baker Stephen M.
Koerner Gregory J.
Simon & Koerner LLP
Sony Corporation
LandOfFree
System and method for computing and encoding error detection... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for computing and encoding error detection..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for computing and encoding error detection... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2586852