close

Вход

Забыли?

вход по аккаунту

?

Патент USA US3078451

код для вставки
Feb. 19, 1963
3,078,443
A. c. Rose:
coMRouNn ERROR coRREcTI-ON SYSTEM
4 Sheets-_Sheet 1
Filed Jan. 22, 1959
BY
wN
Feb. 19, 1963
A. c. ROSE
3,078,443
COMPOUND ERROR CORRECTION SYSTEM
Filed Jan. 22, 1959
61
¿6
,
62
63
64
4 Sheets-Sheet 2
a;
FIG. 2
.
V1 i l
76”
&
36»
f1
i
.5A
|
1
.53,
|
.
l
l
¿A
4
.53A
¿i4
i
„f6
_
/Ia'ßance
.ffy/mls
¿g Elf/_3_1 lmvß|
|fwß|
[fu/ß]
{fi/2J an@
Í
i
î
D
ídívance'
71d
72°
z#
74v
7%
70,08 ßen/er
'
FIG. 3
114
i112
'
76«
»"3”
Feb. 19, 1963
A. c..Ros1-:
3,078,443 _
coMPouNn ERRoR CORRECTION SYSTEM
Filed Jan. 22. 1959
4 sheets-'sheet s
Feb. 19, _1963
A. c. ROSE
3,078,443
coMPoUND ERROR CORRECTION SYSTEM
ALAN
BY
C. ROSE
United Statesv Patent O ¿ice
3,078,443
PatentedïfF‘eb‘. 19,» 1963
2
l
which have moderately good errorcorrectingpotentials
3,078,443
CGMPOUNDERÄÚRACÜRRECTEÜN SYSTEM
usually have high-rednn'da_r1cies.A In this regard, proposals
(50301Caivin Ave., Ternana, Qali?.)
17 Claims. (Ci. S40-146.1)
channel capacity by one-half, however, and this is normal
ly not acceptable.
Accordingly, the principal object yof the present `inven-`
to add a number of check- bitse'quad-'to the number of` in
Alan C. Rose, Summit, NJ.
formation bits are not uncommon.
Filed lan. 22,1959, Ser. No. '783,453
This invention relates to error detection and correction
tion is to detect and correct errors in digital signals with
systems for digital data handling systems.
The simplest form of digital error detection involves
the-transmission of each digit twice. If the two’signals
out wasting channel space byy unnecessary redundancy.
In accordance» with one aspect of the present invention
this object is accomplished by sensing >the errorV detectionV
10
are different at the detecting point, it is evident that an
error‘has occurred. The simplest form of error correc
or correction- rates' of the system and 'switching between>
schemes which have diiîerent error detection or correc
tion system involves the transmission of each digital
signal three times.
This reduces the
tion capabilities. Thus for specific, example a high grade
data channel couldnormally` be providedlwi'th` a simpleparity checking error detection scheme in which -every*
Errors may Vthen be-corrected on a` 15
two-out-ot-three basis.
InV the tield of digital data transmission, more sophis
sixteenth bitv would-be a check bit. At the detectora`
counter would detect the number of parity _check failures
occurring -within-a given time period. Whenever the error
redundancy which is required. Thus, for example, a sim 20 rate exceeds a predetermined toleration level,- the channel
ple parity checkcircuit for error detection merely in
would be switched over to agloW redundancy error'correc
ticated arrangements for detecting or correcting errors are
also well’known. These systems vary in the amount ofA
volves th'e addition of an eXtra binary digit or “bit” to
groups 'of 'digits to indicate whether the number of “l’s”
included in the group is odd or even. More speciiically,
the four digit code group 1011 would have a fifth parity 25
be _a check bit, and errors may be correctedy satisfactorily
an even number of "‘1’s.” The parity of'each complete
the channel could be'switched over to an interlaced error
bit added to produce the code group lûlllv/hich includes
group of digits including the check bit is reviewed at the
For error correction purposes several parity checks may
as long as they do not occur too close together. If con
ditions become progressively worse, possibly, as a'result
of -sunspot activity or an electricalstorm, `for example,
correcting system or another more powerful form of error
data receiving> point, and errorsare indicated by a changey
in parity.'
tion system. In-suehasystem one bit in four or so could
correcting arrangement.V These progressive shifts wouldA
30 normally require additional channel space, butÁ the re
be made over different sets of 'digits included in the mes«
sage to be transmitted. Each information digitis in
dundancy'would only be that which isactually required
to keep the errors Within bounds.
In- switching frornone error correction scheme to ari-._
cluded `in vtwo checkv groups. The position of an lerrone
other it is- useful to >determine the rate `at which _errors
ous digit may then be located by the erroneous parity 35 are being corrected-andr also the’rate-'of occurrence of;
check groups. Such a system including four informa
uncorrectable errors or error patterns. Normally, the
tion digits and three check digits is ‘disclosed in R. W.
Hamming and E. W. Holbrook Reissue PatentrNo. 23,
601, granted December 23, 1952,.
signals used in correcting errors are readily available, and
thesevsignals mayY be routed to a iirst error counter. This
first counter may have its output periodically sensed'and
Errors may also be corrected by systems in which digits 40 then be reset to give an error rate indication.Y The more
are arrangedV in 'a matrix and parity checks are formed
sophisticated error correction systems also include ar-`
for the rows and columns. Attertransmissionthe digits
rangements
for indicating the occurrence o_f error >pat
may be regrouped in matrix, and errors identiñed by the.
terns whichare beyond the correction capabilities ofthe
row and‘ column parity check failures. One system of
system. In accordancewith one aspect of‘thepresent4
this gene'ral‘type is disclosed in E. P. G. Wright,'Patent
45 invention the rate of correctable errors andthe ratev of‘l
No..2',653,996,` granted’S'epternber 29, 1953.
occurrencejof` uncorrectable‘errors or error bursts are>>
It has also 'been discovered in thelast yeartor two
determined and this'information is utilized> to increase or
that errors in many systemtend to be grouped. MoreY
decrease the redundancy and theerror'correction capabili
particularly, if there is, for exampleyaprobability oil
ties of the digitalv information channel:l
in 100,000 that a given'bit will be changed in transmis 50
ln accordance with one feature of, the invention a :digital
sion, the probability that the next bit will also be wrong
data handlingA system is provided‘with compoundjencod-Q
may drop to .1 in 10. Thev adverse eilectsofgroups of
ing and'decoding- circuitry inoluding’means forproviding
errors may be reduced’ (l) by providingfor multipleV
error detection and correction `schemes >of--difi’erent redun->A
error ‘correction through'increasing redundancy or (2)
dancies or of diiïerent error handling capacities, and>
by interleaving the digits of several code groups sothat 55 switchingcircuitry is provided for` switchingsaid com
adjacent erroneous digits will`be part of different codev
pound encoding and' decoding circuits from one errori do-l
groups. The individual code groups may be the type ’dis-.
tection'and correction >scheme 'to another.
_
closed in the R. W. Hamming et al. patent cited above;
In
accordance
with
another-featured
the
invention
the
This interleaved or interlaced Hamming code and‘several
systernas set forth in the preceding paragraph'is provided
other coding systems are described‘in some detail‘in’an
with one or more circuits rfor'determining the rate of >oc
article entitled “Evaluation of Some Error’Correction 60 currence of errors, andthe switching circuitsare@c_on-Y
Methods Applicable to Digital Data Transmission”> by
trolled to holdthe errors in the'decodeddatapwithin
A. B. Brown and S. T. Meyerspp. 37 through 55 ofjPart
tolerableA limits. The rate circuits ‘may be, implemented
4 of the 195‘8 IRE National Convention Record. This
by individual counters which count the correctableand un
article also considers “error detection plus rerun”‘ systems
correctable errors, and‘which are periodically'sensed‘and
in which code groups are repeated upon the detection of
reset.
an individual error. In passing, it is noted' that no de
termination of error rates is made in this last mentioned
type of system.
From the’ foregoing discussion, it is clear that there arey
many error detection and error correction schemes- avail
able to theengineer. A review Vof the various codes, how
ever, reveals the following dilemma. First, the codes
Other objects andfeatures, and‘various advantage's‘of
the invention will become apparent from a consideration
of the following detailedi'description and> from the draw
,
70 ings, in which:
FTGURE l is a block diagram of a ’digital transmission
system in accordance with the present invention;
3
auvents
FIGURE 2 illustrates one buñer storage circuit which
may be employed with the system of FIGURE l;
through 56, a shift register 5?», a series of five OR gates
6l through 65, a negation circuit d6 and a delay circuit
dâ. A tape 68 is shown being fed through the tape reader
FIGURE 3 shows a circuit diagram of a switching con
trol circuit which may be used in the system of FIV'
URE l;
FIGURE 4 is a logic circuit diagram of the error count
ers and associated circuits of FIGURE l;
5ft?. For the purposes of the present example, it is as
sumed that live binary digits of information are provided
the source and utilization circuit are included a buffer
noted that advance signals are applied on lead titl to each
at the output of the tape reader 5% each time the reader
is advanced. Such signals are provided by standard
FIGURE 5 shows a simple parity check encoding cir
punched paper tape having a possibility of tive transverse
cuits; and
holes. The output leads 7l through ’i6 from the ta c
FIGURE 6 shows a known error correcting circuit, and 10 reader Sil' provide information signals on leads 72 through
associated circuits for tying in with the system of FIG
76 which represent the binary signals read from the tape.
URE 1.
Lead 7l, however, is always energized when signals are
With reference to the drawings, the overall block dia
read out of tape reader 5u to provide a "i” in the initial
gram of one representative system in accordance with
stage 7E of the shift register
present invention includes a digital signal information 15
The purpose of the marker bit in the first stage of shift
source 12, and a digital utilization circuit ld. Between
register 5S will now be explained. Initially, it may be
storage circuit 16, a compound encoding circuit lf3, a
stage of the shift register' 58. These signals must, of
compound decoding circuit 2li, and several special con
couse, be supplied from the encoder, as the rate of ad
trol circuits. These special control circuits include the 20 vance of the signals varies in accordance with the re
master source of timing signals 22, the two error counters
dundancy of the particular encoding scheme which is em
24 and 2d for determining error rates, and the error evalu
ployed. Now, as the shift register
is emptied by the
ation and switching control circuit 28. Although the
transmission of information through the switch 41 to the
counters 2d and 26 and the evaluation and control cir
encoder designated 82 in FIGURE 2, the “l” which was
cuit 28 are shown as separate blocks in FIGURE l, some 25 initially in register stage 78 is advanced to the right. It
of the evaluation circuits are closely tied in with the count
ultimately appears in shift register stage Sd. At this
er output circuits, as developed below.
time the remaining stages of the shift register are empty,
The illustrative circuit of FIGURE l is shown pro
or have “O’s” stored in them.
vided with three or more encoders Sti', 32 and 3ft», and de
ïhe logic circuit including the OR circuits 6l through
coders 36, 38 and ¿tu corresponding respectively to the 30 d5 and the negation circuit 66 is designed to sense the
three encoders. While only three sets of encoders and
presence of live {ì’s in the first live stages of the shift
decoders are sho-wn in FIGURE l, it is to be understood
register 5S, and to provide a signal on lead S6 which this
that a greater number of encoding and decoding schemes
situation occurs. A negation circuit produces an out
may be employed.
put pulse when no input pulse is applied to it, and pro
In switching from one encoder scheme to another, a
number of switches are required. These switches ¿all
through 45' serve to couple the information source, the
data link, and the digital utilization circuit to the ap
duces no output signal when an input pulse or “l” is
supplied to it. Now, with the “l” initially located in
shift register stage 7S, one of the tive OR circuits 611
through 65 is energized as the code group is read out
of register 5g, and produces a pulse at the input to the
the switch d5 supplies signals which correlate the buffer 40 negation circuit 66. Accordingly, no output signal can
storage timing with the internal timing of the various en
appear on lead S5. When the “l” reaches stage S4 of
coders 30, 32 or 34. The switches ¿il through 4S are
the shift register 58, however, the input signals to all of
operated in synchronism by the switching control circuit
the OR circuits 6l through 65 are “O’s”, and the negation
28. Under any given set of operating conditions the
circuit d6 therefore produces an output signal on lead
switching control circuit 23 will set the switches 4l
This serves to advance the tape reader Sii and to
through 45 to select an encoding and decoding scheme to
supply a new set of binary digits to the leads 72 through
provide adequate error control. When error conditions
'76. Following a ’brief delay provided by the delay cir
change, the changes in error rates are detected by circuits
cuit tiä, gating signals are applied to the AND circuits
24 and 26. After a correlation of the change in error
51 through 55. The new group of five binary digits and
rate by circuit 2S, the switches 41 through 45 may be
the marker “l” are then entered into the shift register
shifted to increase or decrease the error correction capaci
58. It is to be understood that the advance of the tape
ty of the system. Thus, for example, with an intermedi
reader Sd and the feeding of the new data into the shift
ate error rate, the coding scheme represented by the en
register 5S occurs during a fraction of a shift interval so
coder 32 and the decoder 3S may be connected to the in
that there is no delay in the transmission of digital in
formation source 12, the data link, and to the digital utili 55 formation to the encoder S2. lt may also be noted that
zation circuit 14. If the rate of errors decreases, how
the marker “1” initially stored in shift register stage '7S
ever, it may be possible to use the simpler error checking
is cleared from shift register stage 841' by the transmission
circuit including the encoder 3€) and the decoder 36. As
of new information from the tape reader Sil through the
noted in block 31?, the simplest scheme may merely in
AND circuit Sd to the shift register stage tid. Accord
clude a parity check and may not provide any error cor 60
ingly, the marker bit is not transmitted on to the encoder
rection whatsoever. As error rates build up, however, a
82.
`
shift would be made under the control of circuit 2S to
The
circuit
of
FIGURE
3
represents
a portion of the
the encoding scheme represented by encoder 32 and de
error evaluation and switching control circuit 28 of FIG
coder 3S. A further increase in the error rate could re
sult in shifting to a more powerful error correcting scheme 65 URE 1. In addition, it shows schematically the tie-in
between the circuit
and the switches 4l through 45
as represented by encoder 34 and decoder
Such an
of FIGURE l. Thus, in FIGURE 3 the switches 4l
encoder could involve digital blocks of significant length
and 4t2 each include a series of AND gates. More par
and a redundancy of 50% or more, by way of example.
ticularly, the switching circuit dll includes the AND gates
FIGURE 2 is a detailed block circuit diagram of a buil
91 through 94 and the switching circuit 4.2 includes the
er storage unit which may be employed in accordance
AND gates 95 through 93 and the OR circuit 99. The
with the present invention. The buffer storage circuit
signals from the buffer storage circuit of FIGURE l are
shown in FIGURE 2 is only one of a number of such
applied on lead MP2 to all of the AND gates 91 through
circuits which could be employed in the implementation
94 in parallel. The enabling input to one of the AND
of the circuit of FIGURE l. The circuit of FIGURE 2
circuits 91 through 9d is supplied by the stepping counter
includes a tape reader 5t), a series of ANI) gates Sil
104. One and only one of the AND circuits 91 through
propriate encoding and decoding circuits. In addition,
3,078,443'
94|.-isv enabled by signalsfrom the output of. onev of the
stages» of the stepping counter 104.
The state ofthe stepping counter 194 isl determined. by
signals applied to the advance. lead 106 and to the “step
back.” lead’liißat the input> to thestepping- counter 1114.
I'nthe case: of thefadvancing of--the control counterlûd».
of«FIGURE`-3,:a-signal is applied .to the. AND circuit 138.
from .the ORv circuitlâó.. This occurs whenthe :correct
able errorcounter 122is in one of its higherstatesor-.when
Thus, for example, it‘is initiallyassumed that the stepping
the Auncorrectableerror»counter 124.,.is in one-.of apre
determined number of its higher» states.. Thus, for-spe
ciñe. example,with reference. to.- FIGURE 14, if the counter
counter‘is in-statel. Under= these conditions,` the-AND
122 Vis in state...5~ or. arhigher.. state, `or . if> the. error >counter
circuits 91» and 95A are enabled, thus. selecting-encoder
124.is.in_.state=3 .or any. higherstate, kupon the occurrence.
number 1. Now, assuming that error conditions get
of a sense. signalapplied on~lead152-,- an~advance pulse
somewhat worse, an>> advance pulse isappliedto stepping 10 isapplied to.lead.106.=' This means that- if- the rate
counter 104 onv lead 106. Uponthe occurrence of this
of _occurrence of-‘correctableerrors,v orif the number-fof
advance» pulse, the counter1tì4 shifts from its first state
uncorrectable _. errors .exceeds a predetermined _ minimuml
to its'second state. Underthese circumstances, the AND
level in atime interval determinedlby the. rate of occur
circuits 92 andfäô are enabled, selectingencoder numlber
rencel of'sense and -reset pulses, thefsystemiwill bel stepped`
15
2. Encoder. number 2 hasmore error correction cap
to theînext more powerful :typeof error correcting scheme.
abilities than the first encoder and, therefore cancope
The lead154 tothefinhibiting linput‘terrninal of inhibit
withthe worsened error conditions.` The applicationA of
unit134 isconnected to receive-signalsfrom the switching.
additional advance signals on lead 166 will step the
circuit v142.. associated with coun-ter122.- This arrange
counter 104. progressively toestates 3, 4 or 5. Eachv ad
ment is intended to. handlethe` situation _whereoccasional
vance step Aapplied' to lead Midindicates that the error
infrequent .bursts of. noise. completely ob‘literate a portion
rateV was. not tolerable under the error conditions and
of the. incoming` message. Under these circumstances',
using-the encoding and decoding circuit which was con«
thecorrectable error-stepping counter willîremain in` one
nectedatthe time thepulsewas received- on the advance
of its ylowerrnost. states. However, .the uncorrectab'le er-`
leadflûá. In the exampleshown'in. FIGURE 3, four
ror stepping` counter may reach state^3 or 4,1 for example.
25
encoders. of progressively increasing error correction
Under these conditions, it isnot worthwhile tosteplto
capacity.. are provided. Now, when theerror correction
the. next higher or morepowerful error correcting scheme.
capacity.. of. the fourth encoder is exceeded, the stepping
Accordingly, an inhibiting. signaljapplied on leadf‘15‘4
counter reaches state 5. Under these conditions, the
fourth or “nth” encoder is maintained energized through
prevents the applicationof anoutputpulse throughgthe
.the OR'-circuit.11tì.
Immediately. following.` the application vof , sense signals
to the leads. 15d` andJ1'52, resetsignalsare" applied to leads
-153'andf16i). The. timeinterval'between successive sets
of sense and reset pulsesis determined by the` master-
In addition, however, the alarm 30
circuit 112 .is. energized toÁ indicate that the error rate is
abovethe toleration level for the entire system.
AND circuit-135.58v to the-output lead 166,
Thev delay circuits 114, 116, 118 and 120- are provided
to indicate the padding delayy necessary inthe course of
timing circuit >22..'l This. time.interval‘could,_for example;
switching from one error correction scheme to another. 35 be a matter offone or. more hundre'ds‘of' digit periods of
Thus, the encoder- circuitry associated with each scheme
will have anumber of digit periods yof delay .from input
to- output. A delay such as that indicated by the delay
units.114, 116-118 or 120 is required in-order to avoid
the'messagetransmitted on'the >data link. Suitable time
intervalsmay readily'jbeAdetermined'by one' skilled‘in the
art’by the lerror 'characteristics of‘thefdata link. Thus,
for example, in cases'wherethe'datalink is subject'to
eliminating information digits in-the course of. shifting 40 rapid _fluctuations inthe error rate, relatively `short time
from one encoding scheme to the next.
For ease- in ac
intervals between’ successive sets` of' sense andreset pulses
commodating such switching, it would be desirable that
each of the encoders include the same number of digit
would lb_e required. On the other hand, wherethe‘rate
periods of delay. This may be accomplished by adding
in'glyflongertime intervals between the pairs> ofsensc
ofichange of'theerrorjrate is relatively'low, correspond
al ser-ies delay circuit within each of the encoders to 45 a'n`d_'_reset pulses~ are' permissab‘le. In general,- however,
make. the total delay- provided by eachencoder identical.
relatively short intervals' are" to jbe Vvpreferred ' in >order to
FIGURE 4 shows the two error counters 122 and 124.
Correctable erreors are received at the OR circuit 125
minimize thenecessary equipment in the required-control
circu’itsi
The circuit OFFIGURESÄS a‘simple- parity check-cir
cuit which ’couldîbe employed,l for example, as> theîencoder
and applied to the advance lead 126 at the input to the
error counter 122. Signals indicating errors which are be 50
yond the capacity of the error correcting scheme which
31B 'shown in FIGUR'E‘I.y Theîcircuit of FIGURE 5’ is-an
is currently being employed are applied'to the OR circuit
“even” parity check encoder- circuit; that is, it provides la
128, and from. this ORcircuit to the advance lead 1300i
parity'che‘cli, pulse if the number of information check
the counter 124. Theerror evaluation circuits associated
pulsesis odd, Aand. thus' makes the' total - numberf'ofA pulses
with the counters 122 and 124 include the AND circuit 55 in agiven “word”"‘or"code group'even. In a. circuit of
132, the inhibit circuit 134, the OR circuit 136', and the
FIGURES, lSÍinformation' bits >orbinary digits are trans
ANDcircuit 138; Input signals to the error evaluation
mitte'd‘, a-nd‘this'4 group of fifteen lbits is-ïfollewed by a single
circuitry are supplied from switching networks 141i and
parity‘chec‘k bit. `Such‘a group ofl standa-rdlength code
142 at the output‘ of the error counter 122, and from
groups> is known'asA a “word’fin digital computer termi
switching network. 144 at the output of error counter 12.4. 60 nology.. The timing for the_fy parity check encoder» of
In addition, signals from the “G” state of error counter
FIGURE v5Y is` provided bythe ring counterv16ét.k This
124A are supplied as one ofthe controlling inputs to the
ring counter 164 has' sixteen'states. The first-ñfteen states
AND circuit 132. A second input lead 146'to the AND
are'connected to the inputs ofthe OR circuit 166.Y Out
circuit 132’is enabled by the switching circuit 14S. It is
put signalsjfrom the~ OR; circuit‘166 are» applied-onïleads
apparent, therefore, that the AND circuit132 is controlled 65 168 througlrthe switch 45" of FIGURE'l to thebuiîer
by signals from the "0” state of the counter 124and from
storage circuit’lóï The. determination ofthe odd-oreven
the first few stages of counter 122. Thus, if there are
character ofthe fifteen input' binary digits is made by the
nouncorrectable errors, and only a very few correctable
errors in a given time interval, the AND circuit 132 is
single stagecounter circuit'17t1; Input information digits
are supplied to the circuit`170 on lead 172’ from the buffer
enabled at the time of occurrence of a sense pulse .on lead 70 store. In additionto being applied to the counter cir
150. Following the occurrence of a sense pulse on lead
cuit 170, theinformation digits are transmitted on lead
150, if both of the other two input leads to the AND
17.4 to the~ OR circuit 176-. After passing through a
circuit 132 have been energized, a pulse will be sup
suitable padding 'delay'circu'it 178, they'- are transmitted to
plied on lead 10S to step the switching control counter
75 the data link- on lead- w01'
104 of FIGURE 3 back one state.
envases
7
The single stage counter circuit 17d includes the OR
circuits 182 and 202, the AND circuit 184, the inhibit
circuit 186, and the single digit period delay circuit 188.
The designation “1D” in the delay circuit les indicates
that it includes one digit period «of delay. The other
circuit components are assumed to operate instantaneous
storage circuit.
The encoding lcircuit of FIGURE 6
has a redundancy of fifty percent, that is one informa
tion bit is transmitted for each check bit. The interleav
ing of information bits from the shif-t register 202 with
>check bits from the parity check circuit 204 is accom
plished by the switch 2196 which is operated under the
ly. The counter circuit is of the dynamic type and in
control of the timing circuit 2%'. It may also be noted
cludes a delay loop through which a pulse may circulate.
fthat the switch 207 which sorts out information and
The `state of the counter is determined by the presence
check bits at the decoder is operated in synchronism with
or absence of a pulse in the loop including the ci-rcuit 10) the switch 206.
'
components 132, 186 and 188i. An initial pulse from
Correction of erroneous signals is possible at the de
lead 172 is inserted into the delay loop by 'the OR cir
l‘coder ythrough the inclusion of each information digit
cuit 182. If there is a pulse circulating in the delay
into two check groups. Each of these check groups in
loop, the application of an additional pulse on lead 172
cludes two information digits and one check digit. Thus,
eliminates the pulse from the delay loop. Thus, for eX 15 for example, the information digits in shift register posi
ample, the pulse circulating through the delay loop will
appear as one input to the AND circuit 164.
The new
tons 7 and 4 of shift register 292 are sampled on leads
2% and 21d, and an appropriate output parity bit from
pulse applied on lead 172 provides the other enabling
circuit 204 is supplied to the switch 2%. The value
input to the AND circuit 184. Under these circum
of the parity signal depends on the parity of the signals
stances, an inhibiting signal »is applied on lead 190 to 20 received on leads 2% and 210. Two parity check groups,
the inhibiting input terminal of the inhibit circuit 186.
each of which include a common information digit, are
This has the effect of blocking the signal which would
yshown at 212 and 211i in diagrammatic form and as
otherwise be transmitted from the OR circuit 182 through
sociated with the digital data link. The first check group,
the inhibit unit 186. The next subsequent input pulse
as represented by the line 212 and its depending arrows,
on lead 172 is, of course, transmitted through OR cir 25 includes the digits C1, D4, and D7. The second check
cuit 182 and starts circulating in the delay loop.
group, as represented by the line 214 and its associated
Upon the stepping of the counter 164 to its sixteenth
arrows, includes the check digit C4, and the information
state, a signal is applied on lead 192 to the enabling input
digits D7 and D10. In 'this regard, it may be noted that
to AND circuit 196. The pulse is designated “W.P. No.
the information digit D», is common to these two check
16,” yas it is a “word pulse” which occurs in the sixteenth 30 groups. Now, at the receiver, the simultaneous occur
rence of failures in two parity check groups which are
culating in the memory loop of counter 1719 out to the
monitored in accordance with the arrows associated
digit period of each “word.” This gates the pulse cir
OR circuit 176, if the counter is in the odd state. How
ever, if the counter is in the even state, and no pulse
is circulating in the delay loop, the output lead 193 is
not energized in the ñfteenth digit period, and no signal
is applied from the output of delay circuit 188 to an
input of AND circuit 196 in the sixteenth digit period.
Accordingly, no pulse is transmitted to the OR circuit
176 or to the output lead 180. This conñrms the even
nature of the parity check signals, as it has been shown
that an additional pulse is added only when the counter
is in the odd state.
The number 16 word pulse is also applied through the
OR circuit 2&2 to the inhibiting input terminal of the in
hibit unit 186. This serves to eliminate circulating pulses
from the delay loop and reset the counter circuit to its
initial state.
As mentioned above, the buffer storage timing circuit
is not enabled during the sixteenth digit period of each 50
Word. Accordingly, no input signal is recevied on lead
172 at this time, and the parity check bit is combined in
OR circuit 176 with the first fifteen digits of the binary
with lines 212 and 214i, would indicate that the informa
Ition digit D7 is in error. It would accordingly be reversed
in the manner described below.
rIhe decoder circuit includes an information digit shift
register having a first portion 216 and a second portion
21S, a check digit shift register 220, a first parity check
circuit 222, and a second parity check circuit 224%. The
check circuit 222 checks the validity of a check group cor
iresponding to that designated by line 212, while the sec
ond circuit 224 checks the parity of the group of digits
corresponding to the line 21d. Failure indications from
the parity check circuits 222 and 224 are indicated on
leads 226 and 223, respectively. The AND circuit 230
is operative to reverse the digit stored in stage ‘7 of shift
register 216 as it is transferred to shift register position 6,
when both input leads from the two parity check circuits
222 and 224 are energized. In addition, a signal is ap
plied to lead 232 to be transmitted to OR circuit 12S
of FÃGURE 4 upon the occurrence of a correctable error.
Signals from the parity check circuits 222 and 224 are
laiso applied to the uncorrectable error detection circuit
word to make a complete sixteen bit word which always
234. The uncorrectable error detection circuit 234 may
includes an even number of digits. It may be noted that 55
take the form as shown in the application of D. W. Hagel
odd parity may readily be employed instead of even
barger noted above. While the error detection 234 may
parity, and is often preferred so that every word includes
be relatively complex, it may also be implemented by rela
at least one bi-t. The circuit of FIGURE 5 may readily
tively simple counter circuits. Thus, for example, in the
be transformed into an odd parity check circuit by the
case of an error indication from parity check circuit 22d
addition of a negation circuit at the input to the AND
60 which is not foliowed by an error signal from parity
circuit 196 from the delay circuit 188.
check circuit 222 after exactly three digit periods, this is
The circuit of FIGURE 6 is more fully disclosed in
a prima facie indication that an error has occurred. In
D. W. Hagelbarger application Serial No. 732,385, filed
View of the fact that uncorrectable error indication from
May l, 1958, and entitled “Continuous Digital Error
the
circuit 234 normally indicates that at least two digits
Correction System,” now Patent No. 2,956,124, granted
have been received erroneously, the pulse doubler 236
October 1l, 1960. The circuit of FIGURE 6 is that 65 is provided. With this arrangement, advance signals to
shown in Ithe Hagelbarger application modified to facili
the stepping counter 124 of FIGURE 4 will represent to
tate inclusion in the system of FIGURE 1 of the present
a closer approximation the actual number of erroneous
application. In the circuit of FIGURE 6, the encoder, in
digits which have been received and not properly cor
the upper portion of the FIGURE, includes the encoding 70 rectcd by the decoder. it is again noted that further de
shift register 202, and its associated parity check encod
tails of the circuit of FIGURE 6 and related scheme
ing circuit 2114. Information digits are supplied from the
which may be used in the implementation of the present
buñer storage circuit through the switch 41 to the shift
invention are set forth in the application of D. W. Hagel
register 2112. Timing signals are supplied from the
barger cited above.
timing circuit 265 through the switch 45 to the buñ‘er 75 With reference to FIGURE l, it is noted that the com
3,078,443
9.
1in
Whenthedata link isf-a digital sorter or store., however,
the direct switching control connections shownin- the
pound.y encoder iläis Imerely intended vto represent the pres
ence of. anumber of different encoding-schemes .of vari
ous. error correcting capacities and/ or redundancies.
presentdrawings are practical andv may be employed.
Additional background material which may. well. be
mentioned for the sake of completeness at this. point in
Similarly, of course, the> compounddecoder 2@ merely
represents. tl1e..use of. various corresponding decoding
schemes. The number. ofencoding and decodingschemes
clude. ar copending..application Serial No. 693,452 of
W. D; Lewisand- myself entitled “MultipleError Cor,
may vary'from two -to as large, a number as is 4desired-or
rection Circuitry,” tiledwOctober 30, 1957 now Patent
required-by the-data link whichv isbeing employed; It
2,954,433, granted September 27, 1960. Theerror cor.
mayalso be noted thatthe encoders.anddecodershave
rectiou scheme. disclosed in that-application is eminently
been _shown- asbeingrelatively independent; however, tim 10 suitable »for inclusion in. the present. compound' error
ing circuitsare shown used in common, and the error
handling sys-tem. ln thisregard, it may betparticularly
correcting and errory evaluationcircuits are. also shown as
noted that both correctable and uncorrectable error-cir.
being» employed jointly. It is also contemplated that .many
cuits»v are provided.. Concerning thelogic circuitv com
ofthe components employed inthe encoders 30,132, and
ponents, such as AND circuits, OR circuits, vand the like,
15
3.4. and in the decodersßá, 38, andr 40'. may be used.in
reference is. made toanearly. article by J. H. Felker en_
common, with switching circuits being provided to-switch
titled.. “Regenerative Amplifier for Digital Computer. Ap
the` needed component fromone error correctingscheme
plications,” which appearedat. pages 1584 through.l596
to the next.
yof` the November v1952` issue -ofy the Proceedings. of the
The=timing circuit 22. of. FIGURE lmay include a
Institute Iof Radio Engin-eers, Volume 40, Number l1.
20
master timingor clock source of pulses and circuitry for
Thecircuits of the present invention may be vimplemented
deriving desired control or program pulses at submultiples
iu-accordance with.thetechnologyv disclosed in the Eelker
of» the clock frequency. Techniques for obtaining program
article, or in accordance with» any. of the many other
or-timing control >pulses are now well known inthe. digital
systems of logic' building blocks which have been dis
'data‘handling art. vThe timing circuit 22 may, for ex
closed». intexts and articles. on this_subjectwhich- appeared
ample, include afast ring counter of the type shown at 25
in the last ten years.
164 in FIGURE 5 of the drawings, anda slow ring
lt-«is .to be understood that the .above-described arrange
counter whichwis advancedby one> state each time the fast
ments-are illustrative of the application of-the principles
ringcounter completes a cycle of operation. By coupling
of lthe invention. Numerous other arrangements.rnay> be
an A-ND circuitto the outputs of` predeterminedstages
devised. by those skilledA in the art Without depart-ing from
30
oîboth counters, a.> digit pulse may hev obtained in any
the4 spiritand scope of the invention.
desired-digit period~ iny theicomplete timing cycle-f of the
timing circuit.
The error detectionschemesl described above generally
involve the addition of checkdigits to `information digits.
rlîhe _principles of thepresentinvention arealso applicable
What is claimed is:
l. A.digital data system» comprising a.source. of. input
digital-signals, compound .single passencoding circuitry
35 including meansy for transmitting-signals in accordance
With-different. digital coding schemes. of ditferentiredun
dancies, compound» decoding circuitry including. means
for decoding signals encoded by. said encoding. circuitry,
to coding schemes in which input digitalsignals are` trans
lated‘in a mannersuch thatthey donot appear directly in
the redundant signalsappliedjto the data link. Onetech
a digital. data link.interconnecting\said-.encoding and
nique for implementing suchA a system could involve- the 40 saiddecoding- circuitry, meansfor generating signalsin
inclusion of atranslation matrix in thebufier storageicir
dicating-the rate of occurrence of4 errors on said data
cuit of 'FIGURE’Z’ between> the leads 71through >'i‘á?and
link„-and means responsive> to. saiderrorrate signals for
the AND` gatesSij through.. 56; When employed in ac
automatically switching said‘encodingand decodingcir
cordance with the present invention, individual transla
cuitry from one of'said different digitallcoding schemes
tion. matrices. providing ditlerent redundancies would be
toY
another.
45
switched into the buñer storagel circuit, and no separate
2: In4 a digital- datal system, a source of input digital
encoding circuit fwouldbe required. In each case, code
signals, a_ compound encoder for adding check digits to
groups sutlixedwith a marker. bit would be inserted inthe
theI input'n digital signals, said”encoder'including'means
bu'ñer circuit shift register at its output end.
lfor transmitting‘signals inaccordance -with different ‘digital
Inthe illustrative system shown in thev drawings, the
`encoding schemes providing y different error correcting ca
error rate signalsaredetermined4 directly. Error rate sig 50 pacities and having >diiîerent redundancies, aY correspond
nals could also- be .derived from the measurement of. a
ing compound decoder for correcting errors-.in the trans
.quantity having
a knownl relationship to the actual error
mitted» signals and' means for automatically ~ switching
from; one of .said-schemes -to another.l
rate.` Thu_s,rfor example, in some systems sunspot activity
bears a known relationship to the error rate. In other sys
3. In. a digital. data system, a source of input digital
tems, electrical storms, the` distance between- stations, and 55 signals, a compound. encoder including meansiontrans
otherfactors havea close relationship to the error rate.
mitting, signals, in. accordance with. different digital; en
vThe term “errorerate signals” as employed in thepresent
codingschemesproviding different` error correcting ca
specifications and claims includes these various‘parameters
pacities and different redundancies, meansfor generating
having-aknown relationship to the actual-error rate.
The datalink of FlGUREV l may be an extended trans
mission facility or a digital sorter or store, forA speciñc
examples. ln the case ofanextended transmission facility,
duplicate.steppingcounters such as .that shown at 104 in
FIGURE B‘maybe provided at the two terminals. De
pendingV onthe. type of error ratedetermination circuit
which is employed, switching control signals mustbe sent
from the decoding terminal to the encoding terminal or
vice versa. In- the casegof indirect parameters, such as
those discussed inthe preceding-paragraph, the signals
may be sent over the data link. When »the error rate sig
nals are detected directlyl as shown in FIGURE 4, how
ever, signals for advancing the switching control counter
or stepping it backmust be transmitted from the decoder
to the encoder on a coded and time-shared basis, or other
60
signals indicating the rate of occurrence of correctable
anduncorrectable errors for the one of `said schemes cur
rently in use, 4and means for automatically switching
'from' one of said-schemes» to another in responsel to said
err-or rate sig-nals'.
4. AA digital data system comprising a'source-of input
digital signals, 'compound> encoding. circuitry including
means'for transmitting signals in accordance with dif
ferent digital coding schemesot different redundancies,
buffer storage lcircuit means connected between said
source and said. encoding circuitry for transmitting input
70 signals to said encoding circuitry. in accordance with tim
ing signals supplied by said encoding circuitry, compound
decoding circuitry including means for> decoding signals
l encoded by said encoding circuitry„ a digital Idata link
interconnecting said encoding and said decoding circuitry,
wise, -depending on traíìîc and other engineering factors. 75
ll
adresse
means for generating signals indicating the rate of occur
providing said system with a single pass parity check
type error correction scheme of higher redundancy than
rence of errors on said data linl; during the processing or'
random input digital signals, and means responsive to
said error rate signals for automatically switching said
encoding and decoding7 circuitry from one coding scheme
.to ano-ther.
said error detection scheme, means responsive to high
error rate conditions for automatically switching fromI
Said error detection scheme to said error correction
scheme, and means responsive to low error rate condi
tions for switching from said error correction scheme to
said error detection scheme.
5. In a digital data system, a source of input digital
signals, a compound encoder for adding check digits to
the input digital signals, said encoder including means
for transmitting signals in accordance with different digital
coding methods providing different error correcting ca
l0
pacities, and means for automatically switching from one ~
of said digital coding methods to another of said digital
coding methods.
6. ln a digital data system, a source of input digital
signals, a compound encoder for adding check digits to
l2. In combination, means for handling digital infor
mation in accordance with different digital encoding
schemes having different error detection and correction
capabilities, first and second error rate circuits, means
for applying signals representing correctable errors for
the scheme currently in use to said ñrst error rate circuit,
means for applying signals representing uncorrectable
the input digital signals, said encoder including means
for transmitting signals in accordance with diiierent digital
errors to said second error rate circuit, and means for
coding schemes providing different error correcting ca
limits.
13. ln combination, means for handling digital infor
mation in accordance with different digital coding schemes
having different error detection and correction capabili
pacities and having diiierent redundancies, means for 20
generating signals indicating the rate of occurrence of
correctable errors for the scheme currently in use, means
for generating signals representing the rate of occurrence
of uncorrectable errors for the scheme currently in use,
switching from one of said schemes to another when
either of the error rates exceeds predetermined toleration
ties, first and second error rate circuits, means for apply
ing signals representing correctable errors to said first
and means for switching from one of said schemes to
another in response to both of said two types of error
error rate circuit, means for detecting uncorrectable er
rate signals.
7. In a digital data system, a source of input digital
signals, a butler storage circuit connected to receive sig
rors for each scheme, and means for weighting the de
tected signals representing uncorrectable errors to pro
trol signals to said buffer storage circuit, said encoder
including means for transmiting signals in accordance
control signals developed from' said error rate circuits.
14. ln combination, a data processing system, means
for providing said system with an error detection scheme,
vide signals approximating the number of uncorrectable
nals from said source, a compound encoder connected 30 received digits, means for applying the weighted signals
to said second error rate circuit, and means for switching
to said buffer storage circuit for adding check digits to
from one of said schemes to another in accordance with
the input digital sivnals and for supplying timing con
with different digital coding schemes providing diiierent
means for providing said system with at least one error
error detecting capacities, and means for automatically
correction scheme by which information is processed at
higher redundancics and with a diiíerent digital code than
with said error detection scheme, means for determining
switching from one of said schemes to another and con
currently changing the rate at which timing signals are
applied to said butler storage circuit.
8. In a digital data system, a source of input digital 40 the rate of occurrence of uncorrectable errors with the
scheme in use at any time, means for determining the
signals, a compound encoder for increasing the redun
rate of occurrence of correctable errors, if any, with the
scheme in use at any time, and means for shifting from
one of said schemes to another in response to the deter
dancy of the input digital signals, said encoder including
means for transmitting signals in accordance with dif
ferent digital coding schemes providing di?lerent error
detecting capacities and different redundancies, means for
mined error rates.
i
l5. ln combination, means for processing digital in
formation in accordance with different digital coding
counting errors for the scheme currently in use during
the processing of random input digital signals, means for
periodically sensing the output of said counting means
and for resetting said counting means, and means for
schemes having different error detection and correction
capabilities, first and second error rate circuits, means for
applying signals representing correctable errors for the
automatically switching from one of said schemes to an 50 scheme currently in use to said iirst error rate circuit,
other in response to the sensed output of said error
means for applying signals representing uncorrectable
counting means.
errors to said second error rate circuit, means for switch
ing from one of said schemes to another when either of
9. In combination, a source of digital input informa
the error rate exceeds predetermined toleration limits,
tion, a buffer storage circuit coupled to said source, a
digital data handling system, a compound encoding cir 55 and inhibiting means for preventing the operation of said
cuit including a simple parity checl: error detection en
coder and a single pass parity check error correction en
switching means to a more powerful error correction
scheme when the correctable error rate is below a pre
a simple parity check error detection encoder and a sin
gle pass parity check error correction encoder, means for
generating error rate signals, and means for selectively
ance with the magnitude of said error rate signal.
17. In a digital data system:
determined level.
coder, and means for selectively and automatically switch
16. In combination, means for processing digital in
ing either said simple parity check encoder or said error 60
formation in accordance with different digital coding
correction encoder into circuit between said buffer storage
schemes having ditterent error detection and correction
circuit and said `data handling System.
capabilities, means for generating an error rate signal in
lO. In combination, a source of digital input informa
accordance with correctable errors only, and means for
tion, a buffer storage circuit coupled to said source, a
digital data link, a compound encoding circuit including 65 switching from one of said schemes to another in accord
and automatically switching either said simple parity
check encoder or said erre-r correction encoder into cir
70
cuit between said butter storage circuit and said data link
in accordance with said error rate signals.
1l. ln combination, a data system, means for provid
` ing said system with an error detection scheme, means for 75
a source of input digital signals;
a compound encoder, said encoder including iirst means
for transmitting signals in accordance with a ñrst
digital coding method providing one level of error
correcting redundancy and also including additional
means for transmitting signals in accordance with a
second different digital coding method providing a
diilerent level of error correcting redundancy;
3,078,443
13
a corresponding compound decoder including means for
References Cited in the ñle of this patent
UNITED STATES PATENTS
decoding signals coded in accordance with said first
method and additional means for decoding signals
coded in accordance With said second method;
a digital data link interconnecting said encoder and
Re. 23,601
said decoder;
means for generating signals indicating uncorrectable
2,892,199
Albrighton et al _________ __ Aug. 6, 1957
2,813,149
2,972,127
2,933,789
Cory ________________ „_ Nov. 12, 1957
Lukoff et al ___________ _.. Feb. 14, 1961
Henning ______________ __ May 9, 1961
211,165
Australia _____________ __ Oct. 24, 1957
errors for the one of said encoding methods in use;
iand
switching means responsive to said error indication 10
2,340,809
2,724,739
FOREIGN PATENTS
means for concurrently switching said encoder and
said decoder from one of said coding methods to
another of said coding methods.
Hamming et al _________ __ Dec. 23, 1952
Hat-ton et ai ____________ __ Feb. 1, 1944
H-arris _______________ __ Nov. 22, 1955
Документ
Категория
Без категории
Просмотров
0
Размер файла
1 416 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа