Note: Descriptions are shown in the official language in which they were submitted.
~8~
MEl'HOI~ ~J~ DEVICE FOR ~ENERATING CHECK BITS PROTECTING
~ D~rA WORD
Check bits are used e. g. for protecting data words
against errors in data processing systems. When the data
word is read into the storage of the system, check bits
are generated in accordance with a predetermined code
rule, and stored in the storage toge-ther with the data
word. Whel1-the data word is read out, check bits for the
read-out data word are again generated and compared with
the oriqinally stored check bits~ The comparison of cor-
responding check bits supplies the so-called syndrome bits.
If all syndrome bits are Zero, -the data word read corre-
sponds to the one that has been written in. If one or
severa] syndrome bits are not Zero, there is an error,
and depending on the code used one or several errors can
be detec-ted, and a limited number of errors can be cor-
rected, by decoding the syndrome bit pattern. Devices forerror de-tection and correction of the above specified type
are described e. g. in US Patents 3 623 155, 3 648 239, and
3 755 797, and they are usually called "ECC" devices.
bependtng on whether the data bits arrive serially or in
parallel, the check bits are generated serially or in
para:llel, too. ~ serial check bit generation is effected
mainly in connection with serial recording devices, as
e, CJ . mac1netic tape ~5 torages. Depending on the type of
~ead~ c~ devicc?, tlle clleck bits can also be generated in
ti~e hyte-serial mode (~lS Patents 3 851 306 and 3 868 632).
The disadvantage of al~ those known devic2s is that they
are designed for one specific purpose. Once an ECC device
is designed it can be used for one specific code only,
and is furthermore applicable either for serial or for
par~llel operation only. Regarding the number of bytes in
GE 980 03~
~L
~.
the data word, and the nurnber of bits per byte the ~nown
devices are also designed for predetermined numbers only.
When the ECC device is implemented on a semiconductor
chip an existing ECC device can therefore not be adapted
to altered circumstances. In fac-t, a new ECC chip will
have to be developed, which involves far too much time for
many purposes. `
It is therefore the object of the present invention to
provide a method and a device for generating check bits
in such a manner that it can be applied universally.
The byte-serial manner of generating check bits according
to -the invention permits a structuring of the ECC device
which is of a highly universal application. Generating
a parity bit to one respective byte is not code-dependent,
which means that standardized units can be provided for
that purpose. The same applies for the byte-serial applic-
ation of the data bytes to the parity bit generators.
Finally, the parity bit accumulation device does not depend
on the code, either, so that the only code-dependent
feature is the selection of the data bits required for
the generation of a byte parity bit. However, this
selection can be advantageously effected in that gates
are provided which are controlled by a control logic, so
that the respective code used merely determines -the charac-
teristics of the control logic.
According to an advantag~ous irnplementation for such acontrol logic, -to give an example, a read-only storage
tROS, ROM) is provided which can also be of a prograrnmable
design. For such a programmable read-only storage (PROM,
EAROM, ERROM, etc.) numerous forms oE implementation are
known. Programmable logic arrays (PLA) are possible, -too.
GE9--80-034
~8~ D7
Since according to the invention the check bit generation
is effected in a byte-serial mode, there is a certain dis-
advantage as to speed compared with the fully parailel
devices, but for many uses, as e. g. in printers or dis~
play terminals this is of no importance. Compared with a
fully serial device cperating with shift registers, the
speed according to the present invention is much improved.
Of course, the amount of cost and hardware required is much
lower than in the fully parallel devices mostly consisting
of comple~ Excl~sive-Or trees.
Particu:larly the possible use in peripherals, as e. g. in
the above-mentioned printers or display terminals shows
that the invention offers a protection of the data to be
tran~ferred to these devices as realized up to now only in
connection with storages of a data processing system. De-
ve:lopill~J an ECC device suitable for a printer has always
taken too much time, so that in such peripherals the data
words could be protected through simple parity bi-ts only.
~lo~everl this permits the detection but not the correction
of a single error. With the invention, a very rapid adap-
tation of the ECC device to the respective purpose can be
efEected, with the consequence that the few components of
the device as disclosed by the invention which depend on
2r, the code or on the width of the transfer paths, can be
quic~c]y initializecl. An entirely novel development of ~n
ECC se~ .conductor chip, and the production of this chip for
respecti.ve~ly dlfferellt purposes has been rendered super-
fluous by the present invention.
An embodiment of the invention will now be descrlbed with
reference to the dra~ings, which show the following:
Fig. 1 the basic strvcture of an error correcting
device connected to a storage,
GE 980 034
3~
Fiy. 2 the basic circuit arrangement of an embodi-
ment of the invention,
Fiy~ 3 a code matrix,
Fig. 4 a detailed representation of the circuit
arrangement depicted in Fig. 2,
Fig. 5 details of the time control of the arrange
ment in accordance with Fig. 4,
Fig. fi a survey of bit selection signals.
It '~7i.11 first be shown with reference to Fig. 1 how an
error correcting device~ (ECC device) 2 is connected to a
storc-)ge 1 for the writing-in and reading-out of data. ~pon
wrikinc3 in, check bits are generated in device 2 for data
.suppLied by a peripheral unit 3 or by a processor 4 via a
bus 6. 'rogether with the respective data, these check bits
are read :Lnto storage 1 via bus 5. Upon the read-out,
device 2 once more generates check bits for the read-out
data according to the same rule, and these check bits are
compared with the stored check bits. The comparison of two
corresponding check bits results in the so-called syndrome
hit. IE call syndro~e bits are 0 it can be assumed that the
read-out c1ata are tdentieal with the previously read-in
data, i. e~. that ~hf' data have no-t be~t-~n atlverst-~ly affectetl
on b.~lS S or in storage 1. I one~ or several syndrome bits
are no~ 0, thi.s :lndicates a single error or a douhle error
c1epel1ding on the encoding rule selected for yenerating the
check bits. Most ECC devices are structured in such a manner
that single e~rrors can be eorrected, double errors detected,
but errors of a still higher order can be neither detected
nor corrected. If there is a single error, it can be local~
ized al~d corrected tnrough the decoding of the syndrome bit
GE 980 034
pattern. Subsequently, the corrected data are emitted to
the addressed unit via bus 6.
The structure of the ECC devices depends on the number of
data bits in a data word, i. e. on ~he width of the trans-
fer buses 5 and 6, and it is furthermore influenced by
the f~ct whether storage 1 is word-organized, halfword-
org;~nizecl or byte-organized. ECC device 2 can be struc-
turally combinecl with units 1, 3, or 4.
~i~. 2 represents a bclsic circuit arrangement of an embodi-
ment of the present invention. The data to be encoded or
checked are applied to a byte seleetion logic 10. Aeeording
to the invention, the check bits are generated byte-wise,
~s will be deseribed below in detail in eonneetion with
Figs. 3 and 4. For better understanding of the generation
of check bits, reference is now made to Fig. 3 showing a
code matrix~ also ealled "H-matrix". In the present case,
the data word is to comprise eight data bytes having eight
data bits eaeh. To this data word, a eheck byte is gene-
ratecl, t. e. eight eheck bi-ts C1 - C8 are produced. To give
an example: Check bit C1 is generated by an addition modulo
2 of all data bits given with a dash in the first line of
-the nlatrix according to Fig. 3. Sinee in the present ease
the overall nu~lber of -the bits per storage loea-tion in
~orage 1 is 72, and sinee 64 bits thereof are data bi.ts
I~Q - ~63, the preser1t code will be called a 72/64 code. ~s
clemol1straked by row I o~ the matrix, a total oE 32 data bits
are usec1 Eor gerleratil1q check bit C1, i. e. bits O - 15,
30 32, 36 - 38, 40, 44 - 46, 48, 52 - 54, 56, and 60 - 62.
herefore, check bit C1 eould be generated by an Exelusive-
OR gate having 32 inp-lts, or through a modulo 2 adder to
whiel1 the respeetive 32 bits are applied suecessively.
GE 980 034
,3~
ll
Tl1e invention makes a new approach in that parity bits are
successively generated to the individual data bytes, and
in ~l~at these byte parities are accumulated in the modulo
~ mode. Tlle accumula~ion results will then correspond to
a parlty hit over the respective data bits of -the eight
data bytes, i. e. in tlle above example over the 32 data
-bits mentioned. Fiy. 2 provides for this purpose byte
selection logic 10 which from the read-in data word
successively seLects the individual data bytes for the
generation o~ the check bit. In accordance with the data
bi~s Marked in the matrix of Fig. 3 a following bit
selection logic 12 selects for each data byte those data
bits ~hich are to be used for generating the check bit.
For the remaining bits of the byte zeros are passed on. The
given byte parity bit is generated by byte parity generation
logic 14 depicted in Flg. 2. The individual byte parities
are summed up modulo 2 in the subsequent accumulation logic
16. ~t tl1e output of logic 16 therefore check bits C1 - C~
are available. If in a read operation the check bits to the
~o read-out data are once more generated and compared with the
equally read-out check bits, accumulation logic 16 supplies
syndrome bits S1 - S8 in the manner described below. An
error detecting and localizing logic 18 supplies the re-
qulred error data by decoding the syndrome bits. The
syndrome bit decoding unit in logic 18 depends of course on
the code used. ~lowever, as this code is al.tered only rarely
a read-only storage can e. g. be used Eor logic 18. Similar-
ly the data bits ~ised for generating a check bit can be
selected by means oE a code implementation logic 20 for
which a read-only storaye can be employed too.
For tlle time control of the device a clock control 8 is
provided. However, this time control strongly depends on
the amount of data bytes provided in a data word, and on
tl1e type of storage organization. The corresponding control
GE 980 034
~8~3~'7
signa~s representing tl~e storage organi~ation and the hus
~iidt~ are thus to be applied to clock control 8 as control
signals. Via a line 80 the storage organization is entered,
i. e. the nu~)er of bytes per storage location (generally
1, 2, ~ or 8 bytes). It is thus taken into account for how
many bytes per storage operation check bits will have to be
generated.
Via 1ine 82 con-trol signals are entered which define the
~-idth of the buses (serially, or 1, 2 t 4, 8 bytes) con-
nected to the ECC device 2. The width of bus 5 general~y
corresponds to the capacity of a storage location~
.
~urtl1ermore, code implementing logic 20 receives via lines
86 and 88 control signals which define the number of re-
quired clock signals depending on the number of bytes, and
the number of data bits per data byte.
~or controlling the other functional units 10 - 18 of
~ig. 2, clock control 8 is connected to these units via
a control bus 84.
Fig. 4 is a detailed representation of the basic circuit
arrangelnent of Fig. 2~ The left side of the Figure shows
t}1e various data inputs. Serially arriving data bits are
read via line 23 into a shift register 26 for serial-
parallel conversion. Vata arriving in parallel are read
into blls 32 via bus 24 and gating circuit 30. With a
nla~ilnuln word :lel1g~ of 64 data bits t this bus 32 has a
3~ width of 64 blts, too. Via bus 27 and gating circuit 30,
shift register 26 ca~l ~lso be connected to bus 32. In a
read operation, i. e. in an operation where a data word and
the associated check bits are read out of the storage, there
has to be a comparison with the newly generated check bits,
as described above. ~or that purpose a gating circuit 28 is
GE 980 034
3~
prov;ded ~ia w}-l:ich either the check byte in the case of a
read operation, or a byte consisting of zeros in the case
of a re~d operation can be entered via bus 29 into the
accumulation :Logic. In a serial read-out operation, such
input is effected via shift register 26, bus 27, and gate
28.
~s descrlbed above, accumulation logic 16 generates check
~lts C1 - C8 in a write operation and syndrome bits S1 -
S8 in a read operation. The check bits reach the storage
via bus 64. The respec~ive data bits applied to bus 24 can
reach storage 1 by bypassing the ~CC device. For that
purpose buses 24 and 64 are connected to bus 5 (Fig. 1).
In a reaci operation, the check byte from the storage is to
be entered into the ECC device via bus 22, and the data
~-its ei ther via line 23 or bus 24. For this process, the
above--mentioned lines are to be conneced also to bus 5 via
suitab]e gates controlled by a read or write signal. For
implemel1ting the possible connections of Fig. 1 suitable
gates bet-~een buses 5 and 6 on the one hand, and buses 22,
23, 24 and 64 on the other are therefore to be provided
whicl1 are suitably controlled by read or write control
signals.
Byte selection logic 10 of Fig. 2 consists of a series oE
Inultiplexors MP~ IPX8. At a first clock time, each
multiplexor passes on byte B0, at A second clock time byte
B1, etc. up to byte l37, to bit selection logic 12. Logic 12
provides for each multiplexor a series of AND gates; e. g.
eight ~ND gate~ 36 t 37...38 are provided for multiplexor
~IPX1, AND gates 40, 41...42 for ~PX2, and finally ~ND gates
44, 45...46 for ~-lP~8. The first inputs of the AND gates are
; connected with one respective data bit output of the multi-
plexors. The respective second inputs of these AND gates
GE 980 034
:
3~7
.' '-I
are connected ~ia a hus 34 to code implementing logic 20.
Sincc there is a total of 64 AND gates 36 - 46, bus 34 is
64 bits ~ide. Code implementing logic 20 is structured in
acc~rdclnce with the matrix of Fig. 3. At the time when byte
0 :is passed on by the eight multiplexors MPX1 - MPX8 the
above-mentioned ~ND gates therefore receive the following
signals:
AND gates 36 - 38 conr1ected to MPX1 are all switched
througl1 (enablecl) at the second input in accordance with
the first row, field "byte 0" of Fig. 3. Of the AND gates
connected to multiplexors MPX2 and MPX3, none is switched
in accordance with the second and third row in the field
"byte 0" of the matrix in Fig. 3. In accordance Wit}1 the
fourth ~o~ however all AND gates connected to ~X4 are
s~itched. Of the AND gates connected to MPX5, those be-
longing to data bits D0, D4, D5 and D6 are switched. The
switching of the AND gates connected to multiplexors 6 and
7 is given analogously in Fig. 3, rows 6 and 7 of fields
20 "byte 0~A Finally, of the AND yates (44, 45.. 46) connected
to multiplexor 8 the AND gates belonging to data bits D3,
D5, D6 and D7 are switched through.
In the ne.Y-t cloc}~ period, when byte 1 of the read-in data
word ls passed on by all multiplexors, AND gates 36 - 46
are switched in accordance with the data bits marked in the
fieEd "byte 1". For eight data bytes, the operation of the
device is continued in the manner described, until byte 7
has been switclled tllrough bit selection logic 12.
The data bits passed on by AND gates 36 - 46 reach a
respective byte parity generator BPG 1 - BPG 8, with
reference nul~ers 50, 52 and 54 being provided therefor
in Fig. 4. Each BPG consists e. g. of a read-only storage
with 25G inputs addressed by the data bits, and one single
GE 9 80 03 4
3~7
output. Since the bi~ary data byte to which the parity bit
is to ~e generated consists of a maximum of eight bits,
256 inputs are to be provided. On the other hand, gene-
rators 50, 52 and 54 have to supply one bit only, i. e.
the pI1rity bit, so that only one single output is to be
pro~ided.
The parity bit supplied by each genera-tor BPG1 - BPG8
reaches a modulo 2 adder circuit in accumulation logic
1~ 16. Tlle modulo 2 adder circuit provided for each byte
parity generator consists according to Fig. 4 of a flip-
flop l,T1 - LT8, and an associated Exclusive-OR gate 56,
57...5~. The output of the flipflop is connected to one
input of the Exclusive-OR gate, and the other input of
I5 this gate is connec-ted to the output of the corresponding
byte parity generator. The output of the Exclusive-OR gate
is connected to the set input of flipflop LT. Owing to the
accumul.1tion of the parity bits received for the eiyht data
hy-tes, check bits C1 - C8 can be directly received after
the eighth data byte at the output of each flipflop.
The above speciEication of the embodiment has shown that
for generating each one of the eight check bits there is
one respective set of functional units. Accordingly, the
fol~owing is provided for the generation of check bit C1:
multiplexor MPX1; the series of AND gates 36, 37, 38; byte
parity geIlerator BPG1; Exclusive-OR gate 56, and flipflop
60. Referring to the first row of the matrix of Fig. 3
which is associated to multiplexor MPX1, ~ytes BO to B7
consequently reach bit selection logic 12 via multiplexor
~PX1. AND circuits 36 to 38 shown in this logic 12 permit
the passing of those data bits only which in the first row
of the matrix are m~rked with a dash. The binary signals
reaching byte ~arity generator 50, and whose value for the
non-switcI1ed AND gates is 0, and which -for the data bits
GE 980 034
`;~
3~
s;~ltc}led in accordance with a first row of the matrix of
Fig. 3 assume the value of the switched data bits, are de-
coded as an address, and the bit at the respective address
in generator 50 is read out to accumulation logic 16.
If the parity bit read out to the Exclusive-OR gate (e. g.
56) equals the bits contained in the flipflop (e. g. 60),
two eql~al binary signals are applied at the input of gate
56 so that a Zero is set in flipflop 60. If both inputs to
gate 56 are non~equal, a One is set in flipflop 60. This
operation corresponds to a rnodulo 2 addition.
For carrying out the comparison necessary in a read oper-
ation between a newly generated check bit and the check bit
stored in storage 1, the read-out check bit is set in the
flipflop via bus 22, gating circuit 28 and bus 29 at the
beginnirlg of the check bit generation. There consequently
remains a zero in the flipflop if the newly generated check
bit C1 equals the read-out check bit C. Otherwise, there
remains a One in the flipflop. The bits which after the re-
net~ed check bit generation, i. e. after the comparison, re-
main in the flipflops and which as specified above are
called "syndrome bits" (S1 - S8) are read via a bus 64 into
an error detecting and localizing logic 18. This logic 18
can also be designed as a read-only storage, the eight
syndrome bits presenting 256 addresses, and e. g. 10 bits
being stored at eaci1 address. The meaning of these bits is
the follo-~ing:
NE: ~ll syndrome bits are zero, there is no error.
SE: A single error has been decoded. According to the code
of Fig. 3, the single error is in a check bit if one
single syndrome bit has the value One, and there is
a single error among the data bits if three or five
GE 980 034
3~7
sync1rome bits have the value One. Depending on which
syndrome bits have the value One the position of the
single error can be localized through decoding in
logic 18.
D~: There is a double error whi_h by using the code of
Fig. 3 can be detected but not corrected.~ In the case
of a double error, an even number (2, 4 or 6) of
syndrome bits have the value One.
Ihe rern~ining seven bits read out of logic 18 indicate the
error location for the single error bit of a total of 72
bits.
The e~ecution with respect to time in the production of the
check and syndrome bits will now be described in detail
with reference to Figs. 5 and 6. Fig. S refers in partlcular
to the generation of the first check or syndrome bit, C1 and
S1, i. e. to the first row in the matrix of Fig. 3.
For generating check bit C1, the 64 data bits DO - D63 are
applied at the input of the ECC device, and for the original
setting of the flipflops LT1 - LT8 a zero byte (8 zero bits)
is applied, or the flipflops are reset. During clock TO,
the zero'th level of the multiplexor MPX1 is switched, and
at the output of the multiplexors data bits DO - D7 are
thus availakle. The signals supplied by code implementing
logic 20 to AND gate.s 36 - 38 consist of nothing but One's,
according to -the first row in Fig. 5. Accordingly, all eight
30 ` data bits DO - D7 are applied to the input of parity genera-
tor BPG1, and the value of each individual data bit can
of course be Zero or One. At the output of generator 50
.~ .
~ parity bit PO is available, whereas at this time a zero
; still re.nains in flipf~op l.T1.
GE 980 034
,
F,ig. 5 ln the next r~)w represents the processes at cloc~
time T1. The Eirst level of the multiplexor is switched
through, and ti1e second data byte B1 with bits D8 - D15
is passed on to the series of AND gates 36 - 38. According
to tl~e fist row in Fig. 3, all these AND gates are switched
throuc~l1, and conse~uently all eight data bits D8 - D15 are
applied to the input of generator 50. At the output of the
generator, parity bit P1 is obtained a-t this time, while in
the meantime parity bit P0 had been added to the original
~ero in flipflop 60, so that the contents of LT1 now equal
p3rity blt P0.
During the subsequent clock periods T2 -to T7, one respective
further level of multiplexor MPX1 is switched, and thus an-
1~ other data byte is passed on. The CRL switching signalsgenerated according to the first row of the matrix of Fig. 3
hy code implementing logic 20, for AND gates 36 to 38, as
wel], as the data bits passed on accordingly to the input
of generator 50 are given in the two corresponding fields
of E'ig. 5. The next column "LT1" of Fig. 5 indicates the
moduLo 2 added parity signals for the respective contents
of flipflop LT1. In the last clock period T8, parity bit
P7 generated in the preceding clock period T7 is added to
the contents of flipflop 60, so that after the expiration
of c]ock period T8, check bit C1 is contained in this flip-
flop.
In a read operation, the above described process is exe-
cuted analogously, wlth the exception that prior to the
starting of the parity bit accumulation, check bit C1' from
the storage is set into the respective flipflop. For that
purpose, the read-out check byte is read, via bus 22, gating
circui.t 28, and bus 29 into flipflops LT1 - LT8 prior to the
generation of the check bits. After the expiration of clock
period T8 therefore the flipflop contains syndrome bit S1.
GE 980 034
llB43q~'7
Eig. 6 once more clear:ly shows the bi-t selectlon signals
generated by code implementing logic 20. The eight rows
oE ~ig. 6 correspond to the eight clock periods TO - T7.
One row of Fig. 6 therefore represents the binary signals
suppliecl during the respective clock period by code im~
p1ementing logic 20, for s~itching the AND gates of bit
selection logic 12. Since in the glven example eight data
bytes ha~-e to be switched, logic 20 also has to generate
8 x 64 control bits for switching the AND gates. It is an
essel1tial feature of the present invention that the re-
spectively used code has an effect only on code implemen-t-
ing logic 20 and on error detecting and localizing logic
18. I.ogic devices 18 and 20 can be advantageously designed
as read-only storages (ROS, ROM, EAPROM, EAROM, PLA, etc.),
these devices being initialized prior to the starting
of the ECC device. All other devices of Fig. 4 do not de-
pend on the code used, so that the device of Fig. 4 can
easily be made in series production and, as described be-
low, on one single semiconductor chip.
,If the maximuM word width of eight data bytes is not re-
quired (:Lines 80, 82, Fig. 2) the number of clock signals
is reduced accordingl~ (lines 86, Fig. 2). This means that
not aLl levels of ~he multiplexors, not all AND gates of
the hit selection logic, and not all sets of functional
units according to Eig. 4 are used, since with a sma]ler
nulnber of data bits (lll1es 88, Fig. 2) the number of check
bits can be srnaller, too. The following practical values
can e. g. be used:
1 data byte : 5 check bits
? bytes: 6 check bits
4 bytes: 7 or 8 check bits
GE 980 034
D7
I'
8 bytes: B check bits.
So the device speclfied in the embodiment of the present
invention is applicable for up to a maximum of 64 data bits
and eight addltional check bits. The device can also be
used for any smaller n~lmber of data or check bits by cor-
respondingly reducing the clock periods, and by corre-
spondingly not using logic circuits shown in Fig. 4, and
non-required sets of functional units. The device as dis-
closed by the invention thus guarantees a maximum universal
~-lppl-i(abi:lity with su~stantially standardized structure of
the individual functional units.
'rhe piilS required for a semiconductor chip with the ECC
device as disclosed by the invention comprise e. g. 101:
10 control connections for clock control 8 (Fig. 2),
and for code implementing logic 20 (Fig. 2),
72 data input connections (buses 22 and 24),
1 serial data input 23,
8 check bit outputs (bus 64),
lO outputs of error detecting and localizing logic 18.
The abo~e-melltiolled number of 101 chip connections can be
tecllllologically realized.
With the integration densities realizable at present the
houslllg of the device of Fig. 2 on one single semicon-
ductor chip is no technological problem, either. Housing
on one single chip is possible in the end through the
b~te-~ise generation of check bits and syrldrome bits, in
GE 980 034
3~7
acc-!r-d~nce willl the invention. This operation permits for
mally uses a pclrtlcularly advantageous compromise between
a fulLy serial mode whlch requires few circuits but is
ratlle~ ;low, alld fuJ:L~ parallel operation requirlng a
gre(lt amount o~ har~ware.
GE 9~0 034
