Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-11-08
2003-06-17
Mai, Tan V. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06581083
ABSTRACT:
BACKGROUND OF THE INVENTION
This application incorporates by reference Taiwanese application Serial No. 80105249, Filed Apr. 2, 1999.
1. Field of the Invention
This invention is related to a means for syndrome generation in a Video/Audio processing system, and more particularly to a generation means and a method for identifying the receiving code words in the compact disk (CD) decoding process.
2. Description of the Related Art
Syndrome generation is a checking process for identifying the receiving code words. The syndrome is generated by multiplying the receiving code words by the checking vectors. The equation of syndrome generation is given as follows:
S
=&Sgr;(
R
i
×&agr;
i
),
wherein S represents the syndromes, R
i
represents the code words, &agr; represents the checking vector, which is a shift byte and i is the order. &agr; is the element of a Galois Field, and the value of it is (00000010)
b
. Taking A, an element of the Galois Field, as an example, the product of A multiplied by &agr;
i
can be yielded by left shifting A by i bit, if i is not larger than 7. If i is larger than 7, the product of A multiplied by &agr;
i
can be generated by the following equation derived from the character of the Galois Field:
&agr;
8
=&agr;
4
⊕&agr;
3
⊕&agr;
2
⊕&agr;
0,
wherein “⊕” is an Exclusive OR (XOR) operator.
For any element of the Galois Field, A, as the Most Significant Bit (MSB) is 1, the product of A multiplied by &agr; is the XOR operation result of (00011101)
b
and the value of A left-shifting one bit. On the other hand, as the MSB is not 1, the product of A multiplied by is the value of A after left shifting by one bit. This left-shifting and XOR operation are so-called shift operation, and therefore &agr; is called a shift byte. Conventionally, as the mathematics characteristic of a Galois Field is applied in the multiplication performed by any software and hardware, table-matching or logic circuit including a large number of the gate counts is necessary.
It is sometimes possible that a compact disk (CD) may suffer from physical damage, for example, scratches, during production or use. To prevent logical continuous data from being lost as a result of the physical damage, a data scramble technique is typically employed during the data-write process of CD read-only-memory (CD-ROM) production. In short, each logical continuous data stream is first divided into a plurality of blocks according to a predetermined algorithm. Afterwards, another algorithm is employed to scramble blocks of one logical continuous data stream with blocks of other logical continuous data streams. The resulting scrambled data are then sequentially and continuously written into the physical spaces of the CD. When, unfortunately, a certain portion of the CD is damaged, the portion of damaged data belonging to one logical continuous data stream may be recovered by the associated un-damaged data of the respective logical continuous data stream via the algorithm. Therefore, in addition to the raw data, some extra data, including control code, sync code, and protection code are added to the raw data to form the complete data in the CD.
In order to prevent data damage or loss, when original data are to be stored in disks, the following encoding operations are sequentially performed: C
3
encoding, C
2
encoding, interleaving, and C
1
encoding.
The interleaving operation re-partitions frames of C
2
coded data into different frames for C
1
coding. After interleaving, if data is damaged, the damaged data is dispersed among different frames of the decoded data, and thus correction probability is enhanced.
Therefore, when data in a disk is read, the following decoding operations are sequentially performed: C
1
decoding, deinterleaving, C
2
decoding, and C
3
decoding. Deinterleaving is a reverse operation of interleaving.
During the process of writing data into the CD, encoding the C
3
code, encoding the C
2
code, interleaving codes and encoding the C
1
code are the essential steps, wherein the C
3
code is encoded by sectors, each sector has 98 frames and each frame has 24 bytes. The C
2
code is encoded by frame. In the step of encoding the C
2
code, each frame has an additional four parity check bytes beyond the 24 bytes output from the C
3
code. The original 24 bytes and the additional 4 parity check bytes are yielded by the following equation:
W
3
×G
2
=V
2,
wherein W
3
is the 24-byte code word matrix of C
2
output from C
3
, which is a 1×24 matrix, G
2
is a generating matrix, which is a 24×28 matrix, and V
2
is the code word of the C
2
code, which is a 1×28 matrix, and also the code word after the C
2
code encoding step.
Similarly, the 28-byte code word of the C
2
code is first processed through interleaving codes, then multiplied by a generating matrix G
1
of the C
1
code to yield a 32-byte code word V
1
. V
1
is the code word after the C
1
code encoding. The 32-byte code word V
1
includes the above 28 bytes from the C
2
code word and the other four bytes of the parity check code. Then, the data after encoding is written in the CD.
While the data is read from the CD, the read source code has to be decoded. The process of decoding includes sequentially the steps of decoding the C
1
code, deinterleaving codes, decoding the C
2
code, and decoding the C
3
code. The steps of decoding the C
1
code include multiplying the read 32-byte code word, which is a 1×32 matrix V
1
, by a 32×4 checking matrix H
1
to yield a 1×4 syndromes matrix S. The equation is given as follows.
S=V
1
×H
1
=[S
0
S
1
S
2
S
3
],
wherein
S
0
=V
0
⊕V
1
⊕V
2
⊕
31
;
S
1
=V
0
⊕V
1
&agr;⊕V
2
&agr;
2
⊕ . . . V
31
&agr;
31
;
S
2
=V
0
⊕V
1
&agr;
2
⊕V
2
&agr;
4
⊕ . . . V
31
&agr;
62
; and
S
3
=V
0
⊕V
1
&agr;
3
⊕V
2
&agr;
6
⊕ . . . V
31
&agr;
93
.
The yielded data are identified to be correct if the values of S
0
, S
1
, S
2
and S
3
are all equal to zero. If not, there must exist errors.
The processes of decoding the C
2
code and the C
3
code include also similar syndrome generation steps. It is therefore not further described herein.
The equation for generating the four syndromes can be represented as followed:
S
j
=&Sgr;R
1
×(&agr;
i
)
j
,
wherein, R
i
represents the receiving code words R
0
, R
1
, R
2
, R
3
, . . . , and R
31
, i=0~31, and S
j
represents the syndromes S
0
, S
1
, S
2
, and S
3
, j=0~3
Let (S
j
)
i
=R
0
×(&agr;
0
)
j
⊕R
1
×(&agr;
1
)
j
⊕R
2
×(&agr;
2
)
j
⊕ . . . ⊕R
i
×(&agr;
i
)
j
, wherein the syndrome (S
j
)
i
is the result for generating recursively for i+1 times.
FIG. 1
is a block diagram of the conventional syndrome generating means. Referring to
FIG. 1
, the code word R
0
is first written in the register
10
, which is the syndrome (S
j
)
0
. At the next timing, the code word R
1
is multiplied by the checking vector (&agr;
1
)
j
using a multiplier
12
. The product yielded by the above-mentioned multiplication operation and the output value of the register
10
are then processed through an XOR operation by an XOR gate
14
to yield the syndrome (S
j
)
1
, and then the syndrome (S
j
)
1
is fed back to the register
10
. At the next timing, similar operation is performed to yield the syndrome (S
j
)
2
. By such recursive operation, the finally yielded syndrome (S
j
)
31
is syndrome Sj.
For every multiplication operation, using the conventional syndrome generating means, table matching or complicate logic circuits have to be utilized. For a syndrome generation, a multiplication operation and an XOR operation are both necessary so that not only a large number of table matching steps have to be taken but also a great number of logic gates are used, which needs large memory capacity and extends the processing period.
SUMMARY OF THE INVENTION
It is therefore an object
Chen Shin Yung
Hu Pei-Jei
Su Wei-Ming
Mai Tan V.
Rabin & Berdo P.C.
Via Technologies Inc.
LandOfFree
Syndrome generator and method for generating syndromes in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Syndrome generator and method for generating syndromes in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Syndrome generator and method for generating syndromes in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3102194