Apparatus for convolutional self-doubly orthogonal encoding and decoding

An encoder and decoder for generating and decoding convolutional codes of improved orthogonality. In an exemplary embodiment the encoder includes a K-bit length shift register for receiving an input serial stream of information bits and providing for each input bit a K-bit parallel output to a self-doubly orthogonal code sequence generator. The encoded symbol stream is threshold decoded iteratively using the inversion of the convolutional self-doubly orthogonal parity code generators.

BACKGROUND OF THE INVENTION 
This invention relates to data encoding and decoding of digital information 
transmitted over a communication channel. In particular, the invention 
relates to coding and iterative threshold decoding of convolutional 
self-doubly orthogonal codes. 
In modern electronic communications, information is generally transmitted 
in a discrete digital format. In various applications such as wireless 
telephonic communications or satellite communications the transmitted 
information signal is susceptible to corruption due to noise in the 
communication channel (i.e., electronic interference in the transmission 
medium). To improve transmission reliability and accuracy, the prior art 
discloses channel coding as an error correcting technique. The two 
principal error correcting techniques are block and convolutional coding. 
In convolutional coding, parity bits derived from a span of information 
bits are added to the information bits for redundancy. The information bit 
span length is called the constraint length. Convolutional codes usually 
operate over long streams of information bits, which could be broken into 
shorter blocks. Whether or not broken into blocks, the streams of 
information bits are encoded in a continuous manner by a simple linear 
apparatus called a convolutional encoder. 
In a basic convolutional encoder, the encoder encodes a stream of 
information bits by breaking the information stream into blocks of N 
information bits and by performing a logical exclusive-or operation on the 
most recently received N bit block. For systematic convolutional encoders, 
the resulting parity bit from the encoder's calculation is appended for 
redundancy to the information bits before transmission. Therefore, the 
final transmitted message will consist of the most recently received 
information bits and the parity bit output of the logical exclusive-or 
operation. 
Variations of this simple form includes convolution encoders in which, for 
example, the encoder calculates parity bits from the most recently 
received eight bit information block and selected information bits of 
pervious blocks. The encoder's coding rate (i.e., the number of 
information bits per parity bits) may also be adjusted to improve 
reliability or accuracy of the decoded information. 
Self-orthogonal convolutional codes are specific types of convolutional 
codes. In self orthogonal convolutional code the transmitted parity bits 
corresponding to each transmitted information bit are generated by the 
encoder in such a way that no two parity equations include more than one 
symbol in common. As a consequence, for decoding, a simple majority rule 
on the parity equations can be implemented for obtaining an estimate on 
each received information bit. 
In order to further improve the reliability of the transmitted data, 
several techniques based on multi-level coding and utilizing the serial or 
parallel concatenation of codes have been developed. Turbo encoding is one 
such technique. Turbo encoding may be regarded as encoding the information 
sequence twice, once using a first encoder, and then, using a second 
encoder but operating on a scrambled or interleaved version of the same 
sequence. In principle, any number of encoders separated by random 
interleavers may be used, but the structure is usually limited to two 
encoders with a single interleaver between them. In these techniques the 
convolutional codes are generally of the recursive systematic type, that 
is, the information bits are not altered by the encoding process and are 
transmitted along the encoded accompanying redundant symbols. A key to the 
improved performance of the Turbo coding technique is that because of the 
interleaving or scrambling between each successive encoder operation, each 
encoder appears to operate on a set of independent information data. 
As to decoding, convolutional codes may be decoded using the well-known 
methods of maximum likelihood sequence estimation techniques such as the 
Viterbi algorithm. Another well-known decoding technique which is 
especially well suited for self-orthogonal convolutional codes is 
threshold decoding. Threshold decoding may be implemented with or without 
feedback and with a hard or soft quantized input. 
Generally, decoding of Turbo codes is performed in iterations of two steps. 
On the first step, the first decoder operates on the soft output of the 
channel pertaining to the code symbols of the first encoder, and provides 
to the second decoder information on the reliability of the decoded 
sequence. Likewise, the second decoder operates on the interleaved version 
of the estimated information sequence it receives from the first decoder 
together with a reliability information measure on that sequence and its 
appropriate code symbols. The process is repeated iteratively whereby the 
second decoder feeds back soft output reliability information to the first 
decoder and the process may be repeated anew any number of times. As in 
the encoding, the interleaving or scrambling allows iterative decoding to 
be performed over a set of uncorrelated observables. 
More specifically, two decoding methods for Turbo Codes have been 
considered. The symbol-by-symbol Maximum A Posteriori Probability, MAP, 
algorithm due to Bahl, et al., "Optimal Decoding of Linear Codes for 
Minimizing Symbol Error Rates", IEEE Transactions on Information Theory, 
Vol. IT-20, March 1976, and the Soft-Input Soft-Output Viterbi decoding 
algorithm, SOVA. See U.S. Pat. No. 4,811,346 issued to Battail and U.S. 
Pat. No. 5,537,444 issued to Nill, et al. Both of these decoding 
algorithms suffer from a rather large computational complexity which 
prompted the development of some simplifying variants. In addition to the 
decoding complexity, Turbo Codes present the further disadvantage of an 
inherent latency or delay which is due to the presence of an interleaver 
and the number of iterations that are required to achieve a given error 
probability. This delay may be quite large, even unacceptable to many 
delay-sensitive applications. In some applications such as encountered in 
wireless communications for example, both the decoder complexity and 
latency conspire to make the traditional Turbo coding technique 
unsuitable. 
Accordingly, it is an object of the present invention to provide a novel 
and improved encoder and decoder based on using convolutional self doubly 
orthogonal codes together with iterative threshold-type decoding. 
It is another object of the present invention to provide novel iterative 
encoders and decoders for convolutional codes without increased complexity 
and latency caused by interleaving. 
It is yet another object of the present invention to provide novel 
iterative hard or soft quantized decoders based on Turbo decoders without 
interleaving or scrambling. 
It is still another object of the present invention to provide a novel 
iterative feedback decoder for convolutional codes with error propagation 
constrained by the coding scheme and weighing of feedback decisions. 
These and many other objects and advantages of the present invention will 
be readily apparent to one skilled in the art to which the invention 
pertains from a perusal of the claims, the appended drawings, and the 
following detailed description of the preferred embodiments.

DESCRIPTION OF PREFERRED EMBODIMENTS 
For Viterbi-like iterative decoding of convolutional codes (i.e., Turbo 
Decoding), an interleaver is used to insure that decoding is applied on 
different independent sets of observables. To obtain the same effect 
without interleaving for iterative threshold decoding, Convolutional Self 
Doubly Orthogonal Codes are implemented. 
FIG. 1 illustrates in block diagram form an exemplary embodiment of a 
convolutional self-doubly orthogonal encoder of the present invention. In 
the embodiment illustrated in FIG. 1, convolutional self-doubly orthogonal 
encoder 30 is of a constraint length K. 
In FIG. 1, shift register 12 receives a serial stream of information bits 
I.sub.t. Upon each clock pulse, the self-doubly orthogonal coder 13 
receives a parallel output of the most recent I.sub.K-1 to the K-1 least 
recent information bits I.sub.0 from shift register 12. 
The self-doubly orthogonal encoder 13 selects a subset L of the K 
information bits in a sequence that meets the definition of 
convolutionally self-doubly orthogonal codes. 
A convolutional code of rate 1/2 is convolutionally self-doubly orthogonal 
code, if for all of the following combination of indices: 
EQU 0.ltoreq.j&lt;J,0.ltoreq.k&lt;j,0.ltoreq.n&lt;J,0.ltoreq.p&lt;n,n.noteq.k,p.ltoreq.k 
1) the differences of generators, (g.sub.j -g.sub.k), are distinct, 
2) the sum of differences, (g.sub.j -g.sub.k +g.sub.n -g.sub.p), are 
distinct and 
3) the sum of differences are distinct from the differences. 
The exclusive-or gate 14 receives the parallel stream of the selected 
sequence of information bits generated by the self-doubly orthogonal 
encoder 13. The exclusive-or (XOR) gate 14 performs a logical exclusive-or 
operation on the L selected information bits, thereby generating a parity 
bit output P. Transmitter 15 receives the parity bit output from the 
exclusive-or gate and the most recent input information bit. 
Transmitter 15 packages the parity bit and the information bit into coded 
messages and transmits these messages through a communication channel. 
The self-doubly orthogonal encoder 13 may also select a subset L of the K 
information bits in a sequence that meets the definition of 
convolutionally self-multiply orthogonal codes. In such encoders the 
encoder generates further sequences such that for all variations of W 
pairs of additional indices q.sub.u and r.sub.u where 1.ltoreq.u.ltoreq.W, 
0.ltoreq.q.sub.u &lt;L, 0.ltoreq.r.sub.u &lt;q.sub.u, n.noteq.q.sub.u .noteq.k, 
r.sub.u &lt;p.ltoreq.k, except for unavoidable cases, the differences of 
g.sub.n for each pair of indices q.sub.u and r.sub.u, (g.sub.q -g.sub.r) 
are distinct, the sum of differences (g.sub.j -g.sub.k +g.sub.n -g.sub.p) 
are distinct, the sum of differences 
##EQU1## 
are distinct, all sums of differences are distinct from all differences, 
and all the differences are distinct from each other. 
FIG. 2 illustrates an exemplary embodiment of a hard quantized 
convolutional self-doubly orthogonal decoder. The convolutional 
self-doubly orthogonal decoder 50 of FIG. 2 illustrates an exemplary 
embodiment of a hard iterative threshold decoder for rate 1/2 
convolutional self-doubly orthogonal codes. Data receiver 21 receives 
messages transmitted through a communication channel. The data receiver 21 
detects and divides the message into its parity and information 
components. The convolutional self-doubly orthogonal encoder 22 receives 
the most recently received information bit I.sub.K-1 from the data 
receiver 21. 
The convolutional self-doubly orthogonal encoder 22 is essentially the 
encoder of FIG. 1. The encoder 22 estimates the transmitted parity bit by 
convolutionally self-doubly orthogonal encoding the received information 
bits thereby estimating the received parity bit. The shift register 23 
receives the stream of received parity bits from the data receiver in a 
FIFO register. The exclusive-or gate 24 receives the estimated 
convolutional self-doubly orthogonal code parity bit and the received 
convolutional self-doubly orthogonal code parity bit from the shift 
register 23. The exclusive-or gate 24 performs a logical exclusive-or 
operation on the estimated and received parity bits. 
The first threshold decoder stage 26 receives the output of the 
exclusive-or operation of the exclusive-or gate 24 (i.e., the syndrome 
bits) and the least recently received information bit I.sub.K. 
FIG. 3 illustrates an exemplary embodiment of a threshold decoder stage 26. 
In FIG. 3, the threshold decoder stage 26 is comprised of a shift register 
with additional logic 41, selector 42, threshold logic apparatus 43, 
exclusive-or gate 44, and a syndrome correction selector 45. Shift 
register with additional logic 41 essentially stores the most recent to 
the least recent results of the exclusive-or gate 24 with the possible 
inversion of some of these results. The shift register 46 receives the 
most recently received information bit and stores the information bit in a 
K-bit FIFO register, thereby storing the most recently to the Kth least 
recently received information bits. The exclusive-or gate 44 of the 
threshold decoder stage 26 receives the least recently received 
information bit and the output of the threshold logic apparatus 43. 
The selector 42 selects a set of the bits stored in shift register with 
additional logic 41 according to the inversion of the convolutional 
self-doubly orthogonal code generation. Selector 42 selects all or a 
subset of the syndrome bits stored in the shift register with additional 
logic 41. The selected syndrome bits were directly calculated from parity 
bits which were derived in part from the least recently received 
information bit. The threshold logic apparatus 43 receives the selected 
syndrome bits from the selector 42 and performs a threshold logic summing 
operation on the received syndrome bits. The threshold value of the 
threshold logic apparatus 43 is preset for each threshold decoding stage 
26. If the sum of the syndrome bits is below the preset threshold of the 
threshold logic apparatus 43, an error correcting signal is initiated to 
invert the least recently received information bit of the threshold 
decoding stage 26 and to activate the syndrome correction selector 45 of 
the threshold decoder stage 26. When activated, the syndrome correction 
selector 45 selects the proper syndrome bits of the shift register with 
additional logic 41 to be inverted. These bits to be inverted are 
identical to those selected by selector 42. The threshold decoder stages 
can be implemented as separate identical stages each operating on the 
error corrected output of the previous stage in order to error correct the 
received information bit. The stages can also be implemented as one unit 
which iteratively error corrects the received information bit based on 
previous error correcting iterations. In each stage or iteration, 
variations in the set of selected syndrome bits which are selected based 
on the inversion of the encoder and the preset threshold can increase the 
accuracy of the decoder. For example, the syndrome bits are selected in 
relation to the preset threshold value such that the number of bits in 
each selected subset is proportional to a decrease in the threshold. The 
iterations or stages are terminated based on application specific limiting 
conditions such as decoder complexity, latency and target error 
performance. These limiting conditions require engineering design for each 
application. 
FIG. 4 illustrates an exemplary embodiment in block format of another 
embodiment of a convolutional self-doubly orthogonal decoder 60. The basic 
embodiment of FIG. 4 is comprised of a receiver 61, a storage device 62, a 
decoding unit 63, and a terminator 64. The receiver 61 receives the 
message transmitted through a noisy channel and separates the message into 
its information and parity bit components. The storage device 62 receives 
and stores in selectably accessible locations the stream of received 
information and parity bits from the receiver 61. The decoding unit 63 
estimates the transmitted information bits from the inversion of the 
parity equation of the transmitted message based on received information 
and parity bits and estimated information and parity bits. The terminator 
64 terminates the iterations of the decoding unit based on application 
specific limiting conditions such as decoder complexity, latency and 
target error performance. These limiting conditions are complex and 
require engineering design for each application. 
The decoding unit 63 essentially implements the inversion of the parity 
equation for transmitted convolutional self-doubly orthogonal code. For 
example, for rate 1/2 systematic convolutional self-orthogonal codes for 
threshold decoding, encoding consists of generating a parity bit P.sub.i 
for each information bit I.sub.i to be transmitted at time, i, i=0, 1, 2, 
. . . , where the parity bit is a function of the current bit and of the 
J-1 previous bits: 
##EQU2## 
where the sum is taken modulo-2, as denoted by the .sym. symbol, with bit 
values +1 or -1, where +1 corresponds to the usual zero bit. The J values 
of g.sub.j specify the convolutional self-orthogonal code being used 
(e.g., convolutional self-doubly orthogonal code), and forms a difference 
set that is, their differences are distinct. 
The decoding process consists of inverting the J parity equations 
associated with each information bit by using only the sign of the 
received bit values. The received value and each parity equation generate 
(J+1) estimates and a weighted combination of these estimates produces the 
maximum a posteriori probability "MAP" value of the decoded bit. The 
weighing values can be determined according to the amplitude of each 
received symbol. These estimates may be approximated by the introduction 
of an add-min operator, denoted by the same symbol .sym., which produces 
the same modulo-2 addition on the sign of the operands but with an 
amplitude value equal to the minimum of the absolute values of the 
operands, that is, 
x.sym.y=sign(x)sign(y)min(.vertline.x.vertline.,.vertline.y.vertline.). 
The approximated MAP decoder then consists in producing a decoded bit, 
I.sub.i, according to the following expression: 
##EQU3## 
where I.sup.e.sub.i,j are the J estimates obtained through parity-check 
equation inversion, and where the outermost sum is the usual sum on real 
numbers. The received information and parity bit streams which were 
transmitted over an Additive White Gaussian Noise, AWGN, channel are 
denoted as I.sub.i and P.sub.i respectively. Calculating the 
Log-Likelihood Ratio, LLR, is simple since the observables in this 
expression are all independent, or equivalently, each Gaussian random 
variable P.sub.i+g .sbsb.j and I.sub.i+g.sbsb.j.sub.-g.sbsb.k appears only 
once in the equation for a given i. 
In the usual feedback form of threshold decoding, when g.sub.j -g.sub.k is 
smaller than zero, the past decoded bits are used instead of the received 
symbol. Hence the decoder equation may be written as: 
##EQU4## 
where the generator values g.sub.j are assumed to be increasing with j. 
These past decisions I are considered close to error-free. However, they 
are in fact random variables which should be treated as dependent random 
variables. 
Iteratively applying equation (1) with a gain smaller than 1 for the 
estimates generated by the parity check inversion equation produces the 
following result: 
##EQU5## 
where the gains a.sup.(m) serve the same purpose as the thresholds above. 
To obtain a more flexible arrangement, we may insert the gains in the 
outer sum and then adjust them individually for each estimate and add an 
overall gain on the received information sequence: 
##EQU6## 
For Viterbi-like iterative decoding of convolutional codes, an interleaver 
is used to insure that decoding is applied on independent sets of 
observables. To obtain the same effect without interleaving, apply 
equation (2) recursively to the transmitted convolutional self-doubly 
orthogonal code for the first two decoding steps, that is m=1 and m=2. For 
m=2 the results of the second step may be written as: 
##EQU7## 
where the past decision of each decoding step has not been expanded into 
its channel symbol constituents. These decisions are assumed to be 
error-free as compared with the channel symbols with which they are 
combined by the add-min operator. A condition on n is added on the 
4.sup.th summation of (3), this condition is needed for a strict MAP 
estimate. To obtain equation (3) as a function of independent observables, 
we observe that the terms (g.sub.j -g.sub.k +g.sub.n -g.sub.p), (g.sub.j 
-g.sub.k +g.sub.n) and (g.sub.j -g.sub.k) need to be distinct for all the 
valid combinations of indices, that is: 0.ltoreq.j&lt;J, 0.ltoreq.k&lt;j, 
0.ltoreq.n&lt;J, 0.ltoreq.p&lt;n, n.noteq.k, p&lt;k. This is however impossible 
without a further condition on n, since g.sub.k may be equal to g.sub.n or 
also since g.sub.k and g.sub.p may be permuted. The condition may only be 
on n or else the parity equation inversion becomes invalid. A condition on 
n only implies that not all estimates of the previous decoder are used for 
the current decoding. A necessary condition would then be n&lt;k. Other 
conditions on n depending on the complexity, the error propagation 
characteristics, and proportion of dependent variable over all the 
observables may also be implemented. 
While preferred embodiments of the present invention have been described, 
it is to be understood that the embodiments described are illustrative 
only and the scope of the invention is to be defined solely by the 
appended claims when accorded a full range of equivalence, many variations 
and modifications naturally occurring to those of skill in the art from a 
perusal hereof.