Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Utility Patent
1998-06-25
2001-01-02
Tu, Trinh L. (Department: 2784)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S756000, C714S790000, C714S781000
Utility Patent
active
06170076
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an error correction encoding method in a digital communications system and, more particularly, to a systematic punctured convolutional encoding method.
2. Description of the Related Art
Error correction is an important feature for a digital modem and many error correction techniques have been suggested. For instance, the use of convolutional codes as error correction codes is widespread in mobile radio communications systems and has been adopted as a standard for an air interface in a CDMA (Code Division Multiple Access) digital cellular system, IS-95.
It is to be appreciated that a code rate, R, of 1/2 (i.e., k
where k is number of bits in an information symbol and n is the number of bits in the code symbol) associated with a convolutional code is non-systematic, and a first code word c
1
(x) and a second code word c
2
(x) are generated from an input information word i(x), respectively, by:
c
1
(x)=g
1
(x)i(x) (1)
c
2
(x)=g
2
(x)i(x) (2)
where g
1
(x) and g
2
(x) represent the code word generating polynomials, where the code words c
1
(x) and c
2
(x) are non-systematic, and where the information word i(x), which is not independent of the code words, can be obtained only by an associated decoder. That is, unlike systematic codes, the k bits comprising the information word i(x) do not typically remain unaltered in a non-systematic code word.
A punctured convolutional code having a code rate larger than 1/2 can be obtained by periodically puncturing the code words c
1
(x) and c
2
(x) generated from equations (1) and (2), using a puncturing matrix A. It is to be further appreciated that a variety of forms of the puncturing matrix are well known in the field. Since the puncturing matrix A is a non-systematic matrix, it follows that the code words generated by use of this matrix are non-systematic punctured convolutional codes.
FIG. 1
is a block diagram of a conventional encoder and decoder of a rate-5/8 punctured convolutional code. Reference character A indicates a puncturing matrix [11101 10111]. It is to be understood that an information word is convolutionally coded by convolutional encoder
11
having a code rate of 1/2. That is, for every 1-bit information word, a 2-bit convolutional code word is generated. Next, to increase the code rate of the transmission encoding process, the convolutional code word is passed through a puncturer
12
having a deleting pattern or puncturing matrix associated therewith. The matrix A results in a punctured code rate of 5/8. That is for every 5-bits input to convolutional encoder
11
, 8-bits are output from the puncturer
12
. The punctured convolutional code word is then transmitted over the communications channel to a receiver which reverses the coding process. That is, the code word is passed through an erasure insertion device or depuncturer
13
which restores deleted bits in correspondence with the puncturing matrix employed in the encoding process. Then, the depunctured word is passed through a convolutional code decoder
14
having a rate of 1/2 which outputs the information word originally input to encoder
11
.
Conventional punctured convolutional codes are not available for a system requiring a systematic data structure because they are all generated from non-systematic puncturing matrices. With data and frames in systematic forms, much of the processing delay can be reduced in a transmission system employing an error corrector and detector which uses CRC (Cyclic Redundancy Check) for error detection. For example, to obtain a transmitted information word from a code word prior to decoding in the case of a current non-systematic convolutional code, a divider is required to divide the received code word by the code word generating polynomial g(x). This divider is composed of linear feedback shift registers (LFSRs), the number of LFSRs being equivalent to the order of the error correction code generating polynomial for the CRC code employed. In addition, the processing delays and operations associated with the detection of the information word from the received code word is a function of the size of the code word transmitted. Hence, processing delay increases with code word size, that is, frame size. It is to be appreciated that frames are large in applications involving high multispeed hard disk drivers or high speed data transmission systems such as, for example, ISDN (Integrated Services Digital Network). In other words, due to a high transmission rate within a very short time, a single frame has many bits or symbols, which implies that a large amount of time is required to obtain an information word. This adds to processing delay-related difficulties since it takes a long time to implement decoding in a conventional Viterbi decoder. It is well known that delay-incurred problems are not negligible in a communications system.
SUMMARY OF THE INVENTION
An object of the present invention is to provide a systematic punctured convolutional encoding method in which a non-systematic code word is converted to a systematic code word.
To achieve the above and other objects, there is provided a rate-l
convolutional encoding method in a digital communication system having a non-systematic convolutional encoder. In the method, first to n-th block code words are obtained by multiplying first to n convolutional code generating polynomials by an information polynomial upon input of an information word, one of the first to n-th block code words is converted to a systematic code word, and a new information word corresponding to the systematic code word is obtained. Then, a convolutional code is generated by encoding the new information code in the non-systematic convolutional encoder. The resulting code word is then preferably processed by a systematic puncturer.
These and other objects, features and advantages of the present invention will become apparent from the following detailed description of illustrative embodiments thereof, which is to be read in connection with the accompanying drawings in which the same reference numerals are used throughout the various figures to designate same or similar components.
REFERENCES:
patent: 4312070 (1982-01-01), Coombes et al.
patent: 4547887 (1985-10-01), Mui
patent: 5042033 (1991-08-01), Costa
patent: 5396518 (1995-03-01), How
patent: 5408502 (1995-04-01), How
patent: 5438590 (1995-08-01), Tzukerman et el.
patent: 5446747 (1995-08-01), Berrou
patent: 5465267 (1995-11-01), Todoroki
patent: 5473601 (1995-12-01), Rosen et al.
patent: 5473727 (1995-12-01), Nishguchi et al.
patent: 5486825 (1996-01-01), Cole
patent: 5497401 (1996-03-01), Ramaswamy et al.
patent: 5511082 (1996-04-01), How et al.
patent: 5535220 (1996-07-01), Kanno et al.
patent: 5537420 (1996-07-01), Huang
patent: 5572532 (1996-11-01), Fimoff et al.
patent: 5592492 (1997-01-01), Ben-Effraim et al.
patent: 5610908 (1997-03-01), Shelswell et al.
patent: 5621761 (1997-04-01), Heegard
patent: 5627538 (1997-05-01), Ferry
patent: 5633881 (1997-05-01), Zehavi et al.
patent: 5668820 (1997-09-01), Ramesh et al.
patent: 5719875 (1998-02-01), Wei
patent: 5721745 (1998-02-01), Hladik et al.
patent: 5734962 (1998-03-01), Hladik et al.
patent: 5742622 (1998-04-01), Claydon et al.
patent: 5745497 (1998-04-01), Ben-Effraim et al.
patent: 5996104 (1999-11-01), Herzberg
Min-Goo Kim, “On Systematic Punctured Convolutional Codes”, IEEE Transactions On Communications, vol. 45, No. 2, Feb. 1997, pp. 133, 135, 137, & 139.
Dilworth & Barrese LLP
Samsung Electronics Co,. Ltd.
Tu Trinh L.
LandOfFree
Systematic punctured convolutional encoding method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Systematic punctured convolutional encoding method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systematic punctured convolutional encoding method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2518982