FIELD OF THE INVENTION

The present invention relates generally to a digital communication system, and more particularly, a digital communication system having a punctured convolutionai coding system and method.

BACKGROUND OF THE INVENTION

In a digital communication system, noise in a transmission channel tends to corrupt bit streams of data being transmitted from a transmitter to a receiver. The impact of noise on a transmitted bit stream can be minimized by coding the bit stream with FEC techniques. One FEC technique currently used in digital communication systems is punctured convolutionai coding.

Punctured convolutionai coding techniques in digital communication systems are known in the prior an as shown by the teachings of the following prior an references which are incorporated herein by reference: U.S. Patent No. 5,029,331. issued on July 2, 1991, to Heichler et al.; U.S. Patent No. 4,908,827, issued on March 13, 1990, to Gates; U.S. Patent No. 4,462,101, issued on July 24, 1984, to Yasuda et al.; Punctured Convolutionai Codes of Rate (n-l)ln and Simplified Maximum Likelihood Decoding, by J. Bibb Cain, George C. Clark. Jr.. and John M. Geist, in IEEE Transactions on Information Theory. Vol. IT-25, No. 1 , Jan. 1979, pp. 97-100; and High Rate Punctured Convolutionai Code for Soft Decision Viterbi Decoding, by Yutaka Yasuda, Kanshiro Kashiki. and Yasuo Hirata. in IEEE

Transactions on Communications. Vol. COM-32, No. 3, March 1984, pp. 315-319.

In general, communication systems using punctured convolutionai coding include a coder for coding a digital input to be transmitted from a transmitter and a decoder for decoding the coded input received at the receiver. The coder includes a convolutionai coding circuit which receives the digital input and outputs a convolutionai coded output. The digital input is coded by the convolutionai coding circuit so that for every k-bits inputted into the convolutionai coding circuit, a

corresponding n-bits, where n > k, is outputted. The k-bits inputted and the corresponding n-bits outputted are referred to as k- tuples and n- tuples, respectively. A convolutionai coding rate for the convolutionai coding circuit is defined as the ratio of the number of k-bits inputted to the number of n-bits outputted. and can be expressed as k/n. For example, the coding rate is 1/2 when for each bit inputted into the convolutionai coding circuit there is a corresponding two bits outputted.

In order to increase the code rate of the coder, the convolutionai coded output is passed through a puncturing circuit which includes a transmission mask circuit and deleting pattern memory for transmitting only selected bits of the convolutionally coded output. The puncturing circuit outputs a punctured output having a punctured code rate of z/q, where z = γ. A punctured code rate of z/q means that for every z input bits inputted into the convolutionai coding circuit q bits are outputted from the puncturing circuit.

The desired punctured code rate is achieved by passing a convolutionai coded output through the transmission mask circuit and puncturing the convolutionai coded output on a block-by-block basis. Each block to be punctured is formed from a plurality of n-tuples and is referred to as a puncturing block. The number of n-tuples used to form each puncturing block is currently determined by recognizing that to provide a punctured code rate of z/q, where z = γk, for a convolutionai coded output of rate k/n, at least γ convolutionally coded n-tuples must be grouped and puncmred as a puncturing block to achieve the desired punctured code rate. Accordingly, the bit length of each puncturing block is equal to γ convolutionally coded n-mples multiplied by the number of bits in each n-tuple. The bit length of the puncturing block can be expressed as L = γn. The puncturing blocks are puncmred according to a deleting pattern which has a length equal to that of a puncturing block. The bits of the deleting pattern have a one-to-one correspondence with the bits in each of the puncturing blocks. Accordingly, the deleting pattern is chosen to have a length that can be expressed as L = γn. The deleting pattern chosen has the miriimum bit length necessary to achieve the desired puncmred code rate of z/q for a convolutionai coding rate of k/n.

The deleting pattern used by the puncturing circuit is an L-length block of ones and zeros, with each one representing a transmission bit and each zero representing a non-transmission bit. (The transmission bits and non-transmission bits are also referred to as non-deleting bits and deleting bits, respectively.) The ratio of ones to zeros in the L-length deleting pattern is chosen to achieve the desired puncmred code rate. It is the ratio of ones to zeros in the deleting pattern that determines the puncmred code rate.

For example, a 2/3 puncmred rate is achieved for a rate 1/2 convolutionai coding circuit by using a deleting pattern of length four (i.e.. L = zn = 2 x 2 = 4). The length four deleting pattern is chosen to have three transmission bits and one non- transmission bit so that the new puncmred rate of 2/3 is achieved.

There are a plurality of different deleting patterns having the same ratio of ones to zeros and having the same bit length but having unique arrangements or patterns of ones and zeros. The arrangement or pattern of ones and zeros in a deleting pattern affects the distance propeπies of the puncmred code. To minimize the bit error rate of the communication system, a deleting pattern having the desired bit length and ratio of ones to zeros is typically chosen in an attempt to optimize the distance propenies of the puncmred code.

To select an optimal deleting pattern once the length and ratio of ones to zeros is determined, a puncturing table of potential deleting patterns in which distance propeπies have been calculated for each deleting pattern can be consulted. Selecting an optimal deleting pattern for a given deleting pattern length and ratio of ones to zeros is well-known as indicated by the following incorporated references: Punctured Convolutionai Codes of Rate (n-l)ln and Simplified Maximum Likelihood Decoding, by J. Bibb Cain, George C. Clark, Jr., and John M. Geist. in IEEE Transactions on Information Theory. Vol. IT-25, No. 1, Jan. 1979, pp. 97-100; and High Rate Punctured Convolutionai Code for Soft Decision Viterbi Decoding, by Yutaka Yasuda. Kanshiro Kashiki, and Yasuo Hirata, in IEEE Transactions on Communications. Vol. COM-32, No. 3, March 1984, pp. 315-319. The optimal deleting pattern selected from a puncturing table is used by the puncturing circuit in puncturing on a block-by-block basis the convolutionai coded output.

A digital communication system having a puncmred convolutionai coding system and method that improves the distance propeπies of the puncmred code and the associated bit error rate is needed. More paπicularly, the puncmred convolutionai coding system and method of such a digital communication system should utilize a more effective deleting pattern so as to achieve better distance propeπies for the puncmred code and an improved bit error rate for the digital communication system.

SUMMARY OF THE INVENTION

The present invention is a digital communication system having a puncmred convolutionai coding system and method. The puncmred convolutionai coding system and method of the digital communication system achieves better distance propeπies for the puncmred code resulting in an improved bit error rate. The distance propeπies of the punctured code and the associated bit eπor rate is improved by convolutionally coding a digital input to produce a convolutionai coded output and puncmring the convolutionai coded output according to a deleting pattern having an extended bit length. As discussed below, puncmring a convolutionai coded output with a deleting pattern having an extended bit length compared to the deleting patterns used in prior an digital communication systems provides for a puncmred code having better distance propeπies. Accordingly, for a digital communication system having a panicular convolutionai code rate and puncmred code rate, the digital communication system of the present invention employs an extended deleting pattern providing for better distance propeπies for the puncmred code.

The improved convolutionai coding system and method is implemented in a digital communication system having a transmitter and a remote receiver. The transmitter of the digital communication system includes a coder having a convolutionai coding circuit for outputting a convolutionai coded output of code rate k/n and a puncmring circuit for outputting a puncmred output having a puncmred code rate of z/q, where z = γk. The puncmring circuit receives the convolutionai coded output and bits of the convolutionai coded output are grouped into puncmring blocks. The puncmring blocks are puncmred according to the deleting pattern on a block-by- block basis.

For a digital communication system having a convolutionai code rate of k/n and a puncmred code rate of z/q, where z = γk, each puncmring block and the deleting pattern have a bit length of L = pγn, where p is > 2. As discussed previously, digital communication systems of the prior an use a deleting pattern having a truncated minimum deleting pattern bit length of L = γn. Accordingly, the deleting pattern bit length of the present invention is a multiple of at least two of the niinimum deleting pattern bit lengths of the deleting patterns used in prior an digital communication systems.

Puncmring the convolutionai coded output according to a deleting pattern having a larger number of bits allows a more optimal deleting pattern to be chosen for the depuncturing circuit. Thus, the depuncturing circuit generates a puncmred code having better distance propeπies and the bit error rate of the communication system is improved.

BRIEF DESCRIPTION OF THE DRAWINGS

Figure 1 is a block diagram of the digital communication system of the present invention.

Figure 2 is a block diagram of the coder of the preferred embodiment.

Figure 3 is a schematic representation of a generic bit stream passing through the coder.

Figure 4a shows an example bit stream passing through a prior an coder.

Figure 4b shows an example bit stream passing through the coder of the present invention.

Figure 5 is a block diagram of an alternate embodiment coder. Figure 6 is a block diagram of the decoder.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

Referring to the drawings, the digital communication system having the puncmred convolutionai coding method and system of the present invention is indicated generally by the numeral 10. As shown in Figure 1. the digital communication system 10 generally includes a transmitter 12 for coding and

transmitting a digital input, and a receiver 14 for receiving and decoding the transmitted, coded input. The transmitter 12 includes the general components of a coder 16 having a convolutionai coding circuit 20 and a puncmring circuit 22 for coding the digital input, and a modulator 24 for transmitting the coded input. As schematically shown in Figure 1 , the convolutionai coding circuit 20 codes the digital input to generate a convolutionai coded output and the puncmring circuit 22 punctures the convolutionai coded output to generate a puncmred output. After the input has been coded by coder 16, modulator 24 modulates the puncmred output and transmits the modulated output to receiver 14. Receiver 14 generally includes a demodulator 26, and a decoder 30 having a depuncturing circuit 32 and a convolutionai decoder 34. The demodulator 26 demodulates the modulated output received from the transmitter 12 and outputs to decoder 30 a demodulated output. The depuncturing circuit 32 outputs a depunctured output and convolutionai decoder 34 decodes the depunctured output and outputs a decoded output corresponding to the digital input.

Referring to Figure 2, the preferred embodiment of coder 16 is shown in more detail. Figure 2 depicts a simplified convolutionai coding circuit 20 that will be used to describe the present invention. Convolutionai coding circuit 20 includes a shift register 36, function generators 40a and 40b, and a multiplexer 42. Shift register 36 serially receives input bits from the digital input which is in the form of an input bit stream. The bits are shifted along k-bits at a time into successive k-bit stages 44 of the shift register 36 with a group of k-bits being referred to as a k-tuple. As is well known, convolutionai coding circuit 16 having additional function generators and multi-bit stages could be provided. The function generators 40a and 40b in the prefeπed embodiment are modulo-

2 adders and are connected to different stages 44 of register 36. Output bits are generated by each generator 40 to form generator bit streams and the generator bit streams are combined together by multiplexer 42 to form a convolutionally coded output. The convolutionally coded output consists of a bit stream of successive n- ples where each n-mple is formed by n-bits. where n > k, and corresponds to a k-tuple inputted into the convolutionai coding circuit. The ratio of k-bits entering the

convolutional coding circuit 20 to n-bits exiting is refeπed to as the convolutionai coding rate, and is expressed as k/n.

The puncmring circuit 22 is coupled to the convolutionai coding circuit 20 and receives the convolutionai coded output. The puncmring circuit 22 includes a transmission mask circuit 46 through which the convolutionai coded output passes and a deleting pattern memory 50 connected to the transmission mask circuit 46. The transmission mask circuit 46 functions to puncture the convolutionai coded bit stream as it passes therethrough to produce a puncmred output. In other words, the transmission mask circuit 46 transmits selected bits in the convolutionally coded output and fails to transmit other selected bits. Because fewer bits are outputted from the puncmring circuit 22 than inputted, the puncmred code rate for coder 16 is larger than the convolutionai code rate. Puncmring circuit 22 outputs a puncmred output having a puncmred code rate of z/q, where z = γk. A puncmred code rate of z/q means that for every z input bit inputted into the convolutionai coding circuit 20, q bits must be outputted from the puncmring circuit 22.

As the convolutionally coded output passes through the transmission mask circuit 46, bits of the convolutionai coded output are grouped together to form puncmring blocks. Each puncmring block includes L-bits from the convolutionally coded output. As discussed in more detail below, the number of bits selected to form a puncmring block is a function of the convolutionai code rate and the puncmred code rate.

Blocks of convolutionally coded output are puncmred according to a deleting pattern stored in the deleting pattern memory 50. The deleting pattern is an L-length series of ones and zeros, with each one representing a transmission bit and each zero representing a non-transmission bit. The deleting pattern bits have a one-to-one correspondence with the bits in each puncmring block, and the ratio of ones to zeros in the deleting pattern is chosen to achieve the desired puncmred code rate. In prior an digital communication systems, the puncmring block and corresponding deleting pattern length was chosen to have the minimum bit length necessary to achieve the desired puncmred code rate. More particularly, each puncmring block was formed from a plurality of convolutionally coded n-mples. The

-8- number of n-mples used to form each puncmring block was determined by recognizing that to provide a puncmred code rate of z/q, where z = γk, for a convolutionai coded output of rate k/n, at least z convolutionally coded n-mples must be grouped and puncmred as a block to achieve the desired puncmred code rate. Accordingly, the bit length of each puncmring block for prior an digital communication systems was equal to γ convolutionally coded n-mples multiplied by the number of bits in each n-mple. The bit length of the puncmring blocks of the prior an can be expressed as L = γn.

The present invention digital communication system provides for an improved convolutionai coding method and system by increasing the bit-length of the puncmring block and the deleting pattern above the minimum bit length required to puncmre a convolutionai coded output to achieve a desired puncmred code rate. As discussed, the minimum bit length of a puncmring block to achieve a puncmred code rate of z/q, where z = γk, for a convolutionai coding circuit of code rate k/n is L = γn. The bit length of the mask block and deleting pattern for the present invention is selected to be a multiple of the minimum block bit length and is expressed as L = pγn, where p is an integer ≥ 2.

The selection of an increased bit length for the mask block and deleting pattern is advantageous because the number of potential deleting patterns that can be chosen to be used by the puncmring circuit increases as the deleting pattern length increases and a deleting pattern having improved distance propeπies is available for selection. Thus, increasing the puncmring block length allows a better deleting pattern to be selected for puncmring circuit 22. Use of a better deleting pattern results in improved distance propeπies of the puncmred output and minimized bit errors during transmission.

Referring to Figure 3, a schematic representation of the flow of a generic input bit stream through coder 16 having a convolutionai code rate of k/n and a puncmred code rate of z/q, where z = γk, is shown. Initially, an input bit stream, depicted by a _n -a _lk , a^-a,,, etc., is inputted into convolutionai coding circuit 20. The input bit stream can be viewed as being formed by a series of k-tuples, with each k-tuple containing k-bits. For each k-tuple inputted into the convolutionai coding circuit 20, a

corresponding n-mple of n-bits. where n > k, is outputted from the convolutionai coding circuit 20 to generate a convolutionai coded output depicted by b _n .b, _n , b ₂ ,-b _2n' etc.

The convolutionally coded output is then inputted into the puncmring circuit 22. The convolutionai coded output is puncmred on a block-by-block basis by the puncmring circuit 22 according to a deleting pattern, c.-c^,,. Each block of the convolutionally coded output and the deleting pattern have a bit length of pγn, where p is an integer > 2. Accordingly, a multiple of n-mples is selected to form each puncmring block so that the number of bits in each puncmring block is greater than the minimum number of puncmring block bits required to achieve the desired puncmred code rate. A puncmred output is then outputted from the puncmring circuit 22 and is depicted by b _n -b _n , b ₂ ,-b _2n , etc., where the bits of the convolutionally coded output that were not transmitted are shown crossed out in Figure 3.

Figure 4a schematically illustrates an example input bit stream of bits 1 0 0 1 passing through a prior an coder, while Figure 4b schematically illustrates an identical example input bit stream passing through coder 16 of the present invention. The prior an coder and present invention coder 16 are of the type generally illustrated in Figure 2 and include a convolutionai coding circuit 20 of rate k/n = 1/2 and a puncmring circuit 22 designed to generate a puncmring code of z/q = γk/q - (2)(l)/3 = 2/3. As shown in Figures 4a and 4b. the input bit stream is first convolutionally coded so that for each 1-bit k-tuple, a 2-bit n-mple is outputted. The n-mples form the convolutionally coded output depicted as 1 1 0 1 1 0

0 0.

The prior an coder shown in Figure 4a punctures the convolutionally coded output according to a deleting pattern having a ratio of ones to zeros of three to one and a length L = γn = 2 x 2 = 4. The deleting pattern of the prior an coder is 1 0

1 1 and generates a puncmred output for the input bits of 1 0 1 1 0 0. In contrast, the present invention coder 16 punctures the convolutionally coded output according to a deleting pattern having a ratio of ones to zeros of six to two (i.e., the ratio of ones to zeros for the deleting pattern of the present invention is mathematically equivalent to the three to one ratio of ones to zeros of the present invention) and an extended bit

length of L = pγn = 2 x 2 x 2 = 8. The deleting pattern of the present invention coder is 1 1 1 1 1 0 0 1 and generates a puncmred output for the input bits of 1 1 0 1 1 0. Because the length of the deleting pattern is larger than the minimum bit length used by prior an decoders, a more optimal deleting pattern can be chosen. The bit length of the deleting pattern of the present invention can be chosen to be any multiple of γn which is greater or equal to 2.

An example of an alternate embodiment of coder 16 is shown in Figure 5. In this alternate embodiment, the puncmring circuit 22 includes a transmission mask circuit 46 located upstream of the multiplexer 42. The transmission mask circuit 46 includes a first transmission mask 46a connected to the first function generator 40a and a second transmission mask 46b connected to the second function generator 40b. The transmission masks 46a and 46b are arranged in parallel with respect to the function generators 40a and 40b such that each generator bit stream can be puncmred by a separate transmission mask 46a or 46b. As each of the generator bit streams passes through its respective transmission mask 46a or 46b, each transmission mask 46a or 46b groups its associated generator bit stream into parallel blocks. The combined parallel blocks of the different transmission masks 46a and 46b together form a puncmring circuit block. The puncmring circuit block is puncmred according to a deleting pattern stored in the deleting pattern memory 50. The length of the puncmring circuit block in corresponding deleting pattern, the ratio of ones to zeros of the deleting pattern, and the arrangement of ones and zeros in the deleting pattern are chosen in the same manner as described for the preferred embodiment. However, each transmission mask 46a and 46b punctures its respective bit stream according to only a segment of the deleting pattern. For example, a deleting pattern of eight bits would be selected for a digital communication system 10 having a convolutionai code of code rate 1/2 and a puncmred code rate of 2/3. (See previous discussion provided in connection with Figures 4a and 4b). The first transmission mask 46a would puncture its respective bit stream according to the first four bits of the deleting pattern and the second transmission mask 46b would puncmre its respective bit stream according to the

second four bits of the deleting pattern. The puncmred bit streams are then combined by the downstream multiplexer 42 which outputs the puncmred output.

Referring to Figure 6, the decoder 30 of receiver 14 is shown in more detail. Decoder 30 includes a depuncturing circuit 52 having a depuncturer 54 and a depuncturing pattern memory 56, and a convolutionai decoder 60. The depuncturer 54 processes the received puncmred output according to an inseπing pattern stored in the depuncturing pattern memory 56. The inseπing pattern coπesponds with the deleting pattern used by the coder 16. A depuncmred output is outputted by the depuncturer 54 and inputted into the convolutionai decoder 60 which corresponds to the convolutionai coding circuit 16. In the preferred embodiment, the convolutionai decoder 60 is a maximum likelihood decoder implemented by a Viterbi decoder. The convolutionai decoder 60 decodes the depuncmred output and outputs a decoded output which is an estimate of the digital input of coder 16.

The present invention is directed primarily to a digital communication system 10 having an improved puncmred convolutionai coding system and method. More particularly, the digital communication system 10 provides for puncmred codes having improved distance properties by puncmring convolutionally coded outputs according to deleting patterns having bit lengths greater than the minimum bit lengths required to puncture a particular convolutionai code to achieve the desired puncmred code rate. The deleting pattern of the present invention has bit lengths derived according to the equation L = pγn, where p is ≥ 2. Using a deleting pattern having an extended bit length provides for improved distance properties of the puncmred output resulting in an improved bit error rate for digital communication system 10.

Specific details of the block elements of the digital communication system 10 described above can be located in many references previously published and a detailed discussion of such is not deemed necessary. Different embodiments and adaptations besides those shown herein and described as well as many variations, modifications and equivalent arrangements will now be apparent or will be reasonably suggested by the foregoing specification and drawings, without departing from the substance or scope of the invention. While the present invention has been described herein in detail in relation to its preferred embodiments, it is to be understood that this

disclosure is only illustrative and exemplary of the present invention and is merely for purposes of providing a full and enabling disclosure of the invention. Accordingly, it is intended that the invention be limited only by the spirit and scope of the claims appended hereto.