Note: Descriptions are shown in the official language in which they were submitted.
I
disclosure of the Invention
This invention relates to electronic communications and,
more specifically, to an improved data transmission and reception
system employing error detection and correction.
It is an object of the present invention to provide an imp
proved data transmission system.
More specifically, it is an object of the present invention
to provide improved data transmission apparatus which coincident
tally transmits plural digits via quadrature phase modulation;
and which encodes the outgoing digital information Jo detect and
lo correct errors in the received information data stream.
Roy above and other objects of the present invention are
realized in a specific, illustrative multi-phase communication
system for simultaneously transmitting plural binary digits which
employs one or more error-check to perform an encoding
on the conveyed information over a period of time The inform
motion and error check digits are then communicated via a trays-
mission channel - as by amplitude modulating phase-orthogonal
carriers.
Upon reception, the incoming information and error check
digits are decoded, and supplied to error syndrome circuitry
which corrects errors which may arise from time two time during
' data transmission.
I The above and additional features and advantages of the
! present invention will become more clear from the following
detailed description of a specific, illustrative embodiment
thereof, presented hereinbelow in conjunction with the accom-
paying drawing, in which:
Fig. 1 is a signal space diagram depicting multi-phase
transmission of the prior art and of the instant invention;
Fig. 2 is a block diagram of transmitter circuitry of the
instant invention;
Fig. 3 schematically depicts receiver circuitry operative
in conjunction with the Fig. 2 transmission apparatus;
Fig. 4 represents a specific, illustrative implementation
of transmitter convolutional encoder circuitry 13 of Fig. 2; and
Fig. 5 illustrates a specific, illustrative implementation
for decoder 41 and syndrome error correcting apparatus 43 utile
iced in the Fig 3 receiver.
Referring now to the drawing and more particularly Fig. 1,
there is shown a signal space diagram for multi-phase, e.g.,
quadrature, transmission. As is per so well known (e.g., for
QPSK or quadrature phase shift keying transmission), two carriers
are independently amplitude modulated along orthogonal (i.e., 90
phase shifted) axes. Thus, for conventional QPSK transmission
one carrier assumes an orientation along the plus or minus X-axis
(0 or 180 phase shift) depending upon one of two bits for the
dubiety encoding; while another carrier resides along either the
plus or minus Y axis (90 or 270 transmission) in accordance
with the binary value of the second bit. Accordingly, an
outgoing QPSK radiation will assume one of the points a-d of
Fig. 1 depending upon the value of the two information bits to
be transmitted. Such QPSK coding is widely employed and basically
has a phase error margin of 45. That is, a received QPSK signal
may vary from its nominal value and still be properly detected
as long as the variation does not exceed 45. Once the 45
limit is exceeded, the received point appears closer to a
different QPSK state and thus an error occurs in one of the
two information bits.
In QPSK transmission, all carriers have a like nominal
amplitude. For purposes of the Fig. 1 description assuming a
unit circle sample space (shown dashed in Fig. 1), the relative
amplitude of each carrier for QPSK transmission permissible
--3--
n 3
transmission states a-d) is always + .
In accordance with the principles underlying one aspect of
the instant invention, eight possible -transmission states, given
by the points a-_ of Fig. 1, are utilized. To determine one of
eight states (vis-a-vis, one of four for conventional QPSK
transmission) a third outgoing phase-specifying digit is developed
in addition to the two dubiety outgoing information values (herein
deemed x2 and Al). This third digit is an error encoding bit
stream and is deemed herein Jo. It will now be apparent from
Fig. 1 that the error correcting additional bit increases the
phase margin for properly recovering a dubiety transmission by
22 1/2 to a total of 67.5 as shown in Fig. 1 (thus effecting
approximately a 2 dub improvement in error rejection).
way of overview, the ability to correct for single errors
lo is imparted to the apparatus of the instant invention by employ-in at the transmitter an additional bit which performs an en-
coding over the two outgoing digital data streams. Moreover, the
encoding is effected over a period of time such that each error
correcting, encoding digit represents information which is in
general descriptive of each of (i) the first (or x2) data bit
and the previous such bits over some plural-digit time interval;
; (ii) the second or Al) data bit and the previous such bits
over a predetermined interval; and (iii) the coding or error
check bit (Jo) data stream over the like interval.
I 11 At the receiver, the recovered information data streams
X2 and Xi are delayed for the number of digit intervals over
which the encoding was performed (as is also the received coding
hit stream Jo). The inverse of the coding operation effected
at the transmitter is then accomplished. If the recovered
information x2, Xi and Jo suffered no errors, the parity will
fully check and the x2 and Al data is simply passed -to an output
utili7~tio~ device or circuit. Louvre, if any error in
reception or receiver data processing has occurred the parity
will not check in the receiver decoding apparatus and then the
error syndrome processing structure will then operate in -the
manner more fully described below to overcome or cure the error
in the received information.
With the above overview in mind, attention will now be
directed to the transmission and receiver apparatus of Figs. 2
and 3 which specifically implement the above discussed overall
mode of operation. Considering initially the transmitter appear-
tug of Fig. 2, a data source 10 supplies two data serial streamsX2 and Al such -that for the instant di-bit-transmission during
each digit or bit time, there exists one binary value for each
of Al and x2. The x2 and Al values are then supplied to a con-
volitional encoder 13 (together with -the internally generated
error or check bit stream output x0 which is fed back into the
circuit). The convolutional encoder includes a number of delay
elements and during each bit time provides a specific output
value x0 which is dependent upon the current and/or past values
of x2, Al and x0 over some interval. A specific embodiment of
the convolutional encoder 13 is shown in Fig. 4 and is discussed
below. Again, suffice it for present purposes that the error
check output bit stream x0 performs an error correction encoding
on both itself and on the x2 and Al data flow. Specific error
detecting and correction codes are per so well known to those
skilled in the art - see, e.g., Fig. 4 and the discussion below.
During each data interval, the then obtaining x2, Al
and I binary values constitute addressing inputs to a read only
memory (ROM) 16 which for each one of-eight input address condo--
-lions supplies three amplitude and one polarity defining input
pa to each of digital-to-analog converters 17 and I The outputs
of the digital-to-analog converters 17 and I supply an analog
level
X I
o
of one-of-three bipolar states sufficient to give rise to one
of the eight permissible transmission points a-h of Fig. 1
depending upon -the input variables x2, Al and Jo.
Roy specifically, with respect to the outgoing quadrature
phase transmission, a carrier source 12 supplies a source of
carrier directly to a modulator 21 wherein the 0 phase carrier
is modulated by the output of -the digital to analog converter
18. The output carrier of source 12 is shifted by 90 in a
phase shifter 15 and is supplied to the modulator 19. The
output amplitude of modulator 19 is controlled by digital-to-
analog converter 17.
Accordingly, in a per so straightforward manner the input
variables x2, Al and Jo to ROM 16 specify one of the eight -trays-
mission points _-_; and the output of ROM 16 acting in consort
with the digital to analog converters 17 and 18 and modulators
19 and 21 generate the requisite two modulated quadrature carrier
signals to implement the desired transmission point. It is
apparent that instead of the shifted amplitude signals of the
QPSK situation considered above, the phase modulated carrier
signals of the instant transmission. system have relative values
~`~ of "O" and + "1" for the assumed unit circle of Fig. 1.
The two modulated quadrature carriers Al and Z2 are then combined
in a linear summing network 26 and impressed upon a communique
lions channel for distribution to any and all intended recipients.
The communications channel may be of any form well known to
those skilled in the art, e.g., radio carrier, wire communique-
lions or the like.
j! Thus, it will be seen that for each digit period, the two
then obtaining characters x2 and x1 - together with the coin-
cidentally present error bit Jo define a specific trays-
mission point of Fig. 1 - and that the phase and amplitude of
the outgoing quadrature carriers in general varies from digit
3 I
period to digit period in accordance with the incoming data
streams and in accordance with the history of -those streams as
reflected by the x0 signal.
At each receiver location (Fig. 3), a reconstituted carrier
source 29 supplies a carrier in phase with -that of the carrier
source 12 at the transmitter. Carrier reconstitution circuitry
is per so well known to those skilled in the art and may be
implemented, for example, by simply multiplying the incoming
carrier signal by a factor of eight to resolve phase ambiguity;
and dividing the eighth harmonic so formed by a factor of eight.
The reconstituted carrier 29 is supplied directly to detector
(e.g., a synchronous mixer and low pass filter) 31. Further, the
reconstituted carrier from source 29 is shifted in phase by 90
in circuitry 33 and supplied to detector 30. The outputs of the
detectors 30 and 31 (which correspond to the analog levels of
converters 18 and 17) are respectively supplied to analog-to-digi-
-tat converters 38 and 36. The output of converter 36 is a three
bit digital word which corresponds in the absence of transmission
error to the input at the transmitter (Fig. 2) to digital-to-
analog converter 18. Similarly, the output of analog-to-digital
converter 38 at the receiver corresponds to the three digital
bits supplied to the digital-to-analog converter 17.
The read only memory (ROM) 40 at -the receiver provides a
, function inverse to that effected by ROM 16 in the transmitter.
In particular, the six bit output of analog-to-digital converters
36 and 38 are address inputs to ROM 40 (and specify the x and
the y coordinates of the received signal point). The ROM 40
includes a stored pattern which converts these inputs to the
equivalent x2, Al and x0 received versions of the original x2
and Al and x0 outgoing data at the transmitter. The use of the
prime designations on the x-underlyiny variables indicates
received versions of the outyoiny data. The x', Al and x0
data will identically equal the x2, x1 and x variables in the
absence of error. Should a -transmission error or receiver
data processing error occur there of course will be a difference
between the two and it is the function of the instant apparatus
to detect and correct that difference and that error.
The received x2, Al and x0 signals are supplied to a decoder
circuit 41 which provides a decoding which is the inverse of that
effected by convolutional encoder 13. The decoder 41 includes
delay apparatus for delaying between its input and output the
x2, Al and x0 signals for an interval corresponding to the
encoding period for convolutional encoder 13. assuming that the
received signals are identical to the transmitted signals, the
decoder 41 supplies on an output lead 42 to a syndrome correcting
circuit 43 characterized by an error-free signaling state (e.g.,
a binary "0") indicating that no errors have occurred. As long
as this situation obtains, the delayed x2 and Xi outputs of
decoder 41 pass without change through Exclusive-OR gates 79
and 81 such that the recovered x2 and Al signals are available
for any desired output utilization purpose. however, when an
error does occur, the output lead 42 switches to its alternate
(assumed "1") state. Depending upon the nature of the error and
the power of the code employed, one or perhaps both of the
erroneous I or Xi variables are corrected in the corresponding
Exelusive-OR gates 79 or 81 by "1" output signal on leads 44
or 45 (since a "1" input to an Exclusive-OR gate will invert
whatever binary level is applied to the other input of an
Exclusive-OR gate). A specific implementation for decoder 41
and the syndrome correcting circuit 43 operative with respect
to the specific encoder 13 shown in Fig. 4 is discussed below
with respect to Fig. 5.
--8--
it
Turning now to Fig. 4, there is shown a specific convolu-
tonal encoder 13 used in the transmitter portion of the instant
communication apparatus (Fig. 2). The apparatus includes an
array of cascaded unit delay circuits 50, 53, 56, 58, 62, 64,
66, 72 and 73, i.e., delays of one digit period for the data
streams I and Al. A plurality of Exclusive-OR gates 52, 55, 60,
63, 65 and 69 are disposed between illustrated ones of the unit
delay elements. As above discussed, it is the purpose of the
encoder to perform an encoding over the x2, Al and x0 digits
over a predetermined number of prior bit intervals. Thus, for
the Fig. 4 encoder, the error bit encoding x0 will include a
measure of the x2 signal from two bit times prior (effected by
delays 72 and 73 through the flow combining effect of Exclusive-
OR gate 69), of the x2 digit four digits prior (delays 64, 66,
72 and 73 with the combining and pass through effects of Exile-
sever gates 63, 65 and 69); and five bits prior (via delays 62,
64, 66, 72 and 73 and their associated Exclusive-OR gates. Semi-
laxly, x0 is also a function of the Al variable occurring 3, 4,
5 and 7 bit times earlier; and of its own error check-encoding
character x0 stream 7, 8, and 9 times earlier. Expressed in
mathematical terms,
x0 = x2 (D + D -I D ) + Al (D + D + Equation 1
D + D + x0 (D + D -I D )
where "D" is an operator representing one unit of delay, "D "
represellts two units of delay, and so forth. Rearranging
Equation 1,
x0 x0 (Do + Do + Do) = x (D + D + Equation 2
Do) + Al (Do + Do = Do -I Do)
and solving for x0,
X2 (D -I D Do) -I Al (Do Do -I Do Do) Equation 3
O
l [Do -I Do Do]
Letting operators Go, Go and Go represent the functional depend
dunce of x0 on x2, Al and x0, respectively, Equation 3 may be
rewritten,
Jo - 2G2 + xlGl Equation 4
1 - Go
For purposes which will become more clear below when operation
of the Fig. 5 decoder 41 is considered, Equation 4 may be
rewritten,
2 2 1 1 0 0 ) Equation S
The negative sign in the last parenthetical expression of Equal
lo lion 5 may be changed to a positive yielding Equation 6,
0 = x2G2 + xlGl + x0 ( 0 Equation 6
since, for the muddle purpose effected by the Fxclusive-OR
gates of the instant apparatus, subtraction and addition yield
identical results. Thus it will be clear from the foregoing
in Fig. 4 that the expression for the output encoding bit
stream x0 is given by Equation 3 (or 4) above and that x0 in
fact is dependent upon events occurring as many as nine digit
times earlier
A specific implementation for decoder 41 and syndrome
correcting circuit 43 operative in conjunction with the Fig.
4 implementation of transmitter encoder 13 is shown in Fig. 5.
The received versions of the transmitted data x2, Al and x0,
viz., x2, Xi and x0, are respectively loaded into nine stage
--10--
shift registers 80, 82 and 85. Nine stages are employed for
the shift registers since nine digit times of data must be
examined to recheck the parity effected by encoder 13 (Fig. I)
which was operative in conjunction with x0 digits occurring
nine digit intervals earlier. The shift registers 80, 82 and
85, operative in conjunction with cascaded Exclusive-OR gates
84, 83 and 87 to recheck the accuracy or parity of the received
digits - in essence employing the algorithm or expression of
Equation 6 above. That is, if the received digits x2, Xi and
lo x0 accurately and identically correspond to x2, x and x0,
Equation 6 will be satisfied and the output of the final
Exclusive-OR gate 87 will be a binary "0" indicating that no
error has occurred. Thus, for example, during encoding the x2
variable was sampled with unit delays of Do, Do and Do.
Accordingly, the output of the second, fourth and fifth shift
register 80 stages 802, 804 and 805 are utilized. Similarly
examining shift registers 82 and 85 i-t will be seen that the
Al received signal is sampled with unit delays of Do, D and D
(corresponding to G in Equations 36) while x' is sampled with
unit delays Do, Do and D as well as a direct ("l") connection
into the final Exclusive-OR gate 87 ("logo" in Equations 3-6).
Again, if no transmission errors were incurred, the output of
gate 87 is and will remain a "0". Accordingly, -the output of
syndrome error correction circuit 43 and more specifically a
error correction pattern storing read only memory (ROM) 89
will have at its output terminals Ho E an array of all "0's"
thus not inverting the outputs of the Exclusive-OR gates 79
and 81. Under this condition, the correct x2 and Al signals
flow out of the Exclusive-OR gates 79 and 81 and appear as the
desired output data x2 and Al.
Conversely, if an error does occur, -the output of -the
Exclusive-OR gate 87 will be a "1" rather than a "0". Earthier
as each error occurs, it will flow -through a shift register 87
also having nine stages each formed of an Exclusive-OR gate and
following unit delay. The particular pat-tern of "l's" and "0's"
at the output of the shift register 87 stage form address inputs
to the correction storing ROM 89 and, for each address input,
the appropriate stored correction signals are recovered and imp
pressed on the output ports Eye Where a "1" appears on the
corresponding ROM 89 output, the output of the respective gate
79 or 81 is inverted thus correcting the desired error. The
particular contents of ROM 89 depends upon the correspondence
between the pattern of detected errors (if any) stored in the
shift register 87 - and the inversion(s) required to correct
that error condition. Again, where the shift register 87 stores
all "0's" indicating no errors, a "0" appears at each of the out-
puts Eye The pattern for Eye for any non-zero address in-
put depends on the particular coding and the like used and may
be empirically or computational derived. Thus, for example,
single or multiple errors may simply be postulated for the no-
ceiled variables x2, Al and x0 - and the pattern in shift
register 87 computed as the error(s) ripple through register 87.
The necessary correction outputs Eye are then computed for
each state of register 87 -- and define the stored three-bit con-
tents of the corrective word stored at the corresponding address
in ROM 89. The process continues for all errors - and error come
binations of interest to define all used address locations in
ROM 89.
Accordingly, the apparatus of Figs. 2 and 3 using the
specific implementations of Figs. 4 and 5 includes data formed
-12-
I
over nine digit intervals upon transmission; and rechecks the
transmitted parity upon reception, correcting any detected
errors. Many forms of codes may be employed depending upon -the
hardware, complexity and code pattern desired for any particular
application.
In accordance with one aspect of the present invention,
stored errors in the shift register stages 87i may be cleared
(after output correction) by employing a feed back path from the
outputs En Ho to the appropriate inputs of the stages 87io The
particular connection patterns of Fig. 5 correspond to that for
the assumed encoding and decoding apparatus 13 and 41, and
effectively comprises the inverse of the delays effected by the
shift registers 80, 82 and 85. Thus, for example, the Ho cornea-
lion signal (corresponding to x0 errors) is connected to the
first, second and third stages 871, 872 and 873 rather than to
the last three stages of shift register 85 in decoder 14. Semi-
laxly, the feed back connections for the El and En outputs are
the mirror inverse for those of the shift registers 82 and 80.
Exclusive-OR gates (e.g., gates 92-94) are utilized where more
than one output resets any particular stage of shift register 87.
Thus, for example, the third stage 873 is reset by both the El
and Ho signals (corresponding to connections from shift register
stages 827 and 857 in the decoder 41. Note also the correspond
in use of the exclusive-OR gates 93 and 94 for the x2 and x
stage 804, 805 and 824, 825 connections of decoder 41. The
above feed back connection is optional and when employed will
increase system performance.
The maximum error correction capability of the code
employed can be achieved if the functions of the decoder 41 and
I the syndrome correcting circuit 43 are cascaded, i.e., if the
-13-
structure of Fig. 5 is replicated with outputs x2 j, Al j and
x0 j for each stage are supplied as inputs to a just stage.
For this purpose, an Exclusive-OR gate 86 is added (shown dashed
in Fig. 5) to correct -the x0~ bit prior -to -the x21 - x0' bitts
being fed in-to a cascaded, following Fig. 5-type arrangement.
This cascade may be repeated as many times as is needed. In
practice, the full capability is achieved in three or four sea-
lions.
The storage pattern for ROM 89 is different for each
stage of the cascade. The first ROM corrects only the most
easily corrected errors. Later ROM's correct the more difficult
to correct errors i.e., multiple clustered errors. This may be
thought of as having the earlier ROM's "clear the field" for the
final correction stage. The final stage does no-t require the
Exclusive-OR gate 86.
The above described arrangement is merely illustrative
of the principles of the present invention. Numerous modifica-
lions and adaptations thereof may be readily apparent to those
skilled in the art. Thus, for example, any number of concurrent
data streams zoom be encoded by any number of error correct-on
digits Xoj~ it simply requiring a signal space having sufficient
transmission conditions to reflect each of the different xi, x
Further, as above discussed, -the specific coding and decoding
implemented may be as elaborate or straightforward as desired by
the user depending upon the economics of any application, con-
side ring cost, signal delay time and the like.
