Note : Les descriptions sont présentées dans la langue officielle dans laquelle elles ont été soumises.
~0~9~2Z
BACK~7ROUND OF THE INVENTIOrll
Field of the Invention
This invention relates to computer sy~tems and tele-
conmmmication systems utilizing computers and more particularly
to a method and apparatus for mani~ulating data to generate a
cycllc redundancy check character, ~nd for utilizing the cyclic
redulldancy check character generated and the data which it re-
presents ~o ascertain that the data has not been altered.
Description of the Prior Art
LO A variety of different forms of error detection are built
into data handling equipment. Such error detecting apparatus
ass~ne particular importance when data is transmitted from one
particular device to another device within a data processing
system or from one data processing syste~ to another, where the
probability of losing or obliterating ~everal sequential bit~
is greater due to noise in transmission. Of course, changing
even one bit would change the sense of an entire message.
Several scheme~ and devices have been utilized in erro~
control. Perhaps the most common method of detecting errors is
the use of parity. ~ith this method, the digits of a binary
word are inspected and an extra digit or bit ~binary-digit) is
added. This digit is chosen to be "zero" or "one", as necessary
to keep the total number of digits in the "one" state either odd
or e~en according to a predetermined co~vention. Another single-
error correcting code is the Hamming code where parity checked
digits are assigned to particular positions where their weights
indicate which digits of the whole code are in error. Still
other techniqueg utilize sur~l checks.
When information is transmitted through data links using
public telephone networks or other such co~munication devices,
-2- ~
the type of error encountered is different from those pre-
viously considered. Because the digits are transmltted
serially, impulsive noise from the communication channel
affects a sequence of ad~acent digits as well. One technique
utilizes a cyclic redundant check character for detecting
such errors. In this technique a finite length of an original
sequence of characters ig divided by an operator to produce a
remainder; the actual transmission comprises the original
sequ~nce followed by the remainder. At the receiver, a similar
L0 division process produces a locally generated remainder fbr
comparison with that sent by the transmitter. Any differences
result frGm the introduction of error sequences which cannot
be divided exactly by the chosen operator.
In implementing this technique additional hardware is re-
quired both at the transmittin~ and receiving end. Ihis hardware
usually takesthe form of an additional shift register, exclusive
OR circuits and comparator. Since computer networks, where one
computer ~ystem communicates with another, are beginning to mush-
room, and since not all computer systems are equipped with this
additional hardware, univer~al checking for transmission errors
via this technique is not f~asible unless the existing hardware
of each existing computer system can be utilized to implement
this technique.
One way of utilizing existing hardware is to provide soft-
ware techniques that utilize a program for manipul~tion of the
data to generate the character. However, such a scheme is too
slow to keep up with the rate of transmission or rec~ption and
of utilization of modern-day data communication systems. ~7hat
is needed is a control means and/or method for utilizing existing
B 30 computer hardware at a rate greater ~ or equal to the rate of
transmission or reception in generating and utilizing a cyclic.
redundant check character. ~oreover, such control means and/or
method should not require additional hardware, and should require
only a modicl~m of modification to any computer system.
OBJECTS OF T~IE INVENTION
It is a primary object of the invention therefore to pro-
vide an improved error control system for a computer ~ystem.
It is another ob;ect of the invention to provide an improved
error control system for a communication channel utilized by two
or more computer systems.
It is still a further ob~ect of the invention to provide
an improved error control system for computers utilized in a
computer network.
Still another object of the invention i6 to provide an
improved error control system for a computer network system
utilizing existing hardware of the network ~ystem.
A more specific object of the invention is to provide an
improved error control system which generates and utilizes a
cyclic redundant check character similar to that generated by
prior art equipment but not requiring additional hardware as in
prior art equipment.
SU~RY O~ THE INVENTION
In accordance wi.h the above and other objects of the in-
vention, there is provided a method and apparatus for assuring
the accuracy of data received by any device in a computer system
from any other device in the same computer system or from another
computer syste~. The existing hardware of a computer system i8
utilized to generate a cyclic redundant check character each time
a unit of data is transmitted. This is accomplished by micro-
programming the Read Only Memory (ROM) of a c~mputer system to
~9~22
control the existing arithmetic logic unit (ALU) and accumulator (AC)
together with the scratchpad memory (SPM) of a computer system to generate
and utilize a cyclic redundant check character. The check character is
concatenated to the right of a unit of data and is transmitted along with
the unit of data with which it is associated. A device receiving the unit
of data together with its check character manipulates them in the same
manner as in generating the check character utilizing its own SPM, AC and
ROM microprogrammed in the same manner as in generating the cyclic
redundancy check character. lf the data received is the same as the data
transmitted, the result of such manipulation is zero.
According to one broad aspect of the present invention, there is
provided the method of generating a cyclic redundant check character in a
general purpose computer comprising: generating a first result by exclusive
OR'ing with a previously generated cyclic redundant check character, the -
new data for which a cyclic redundant check character is to be generated;
left shifting the first result by a predetermined number of bits; generating
a second result by exclusive OR'ing the unshifted first result with the
left shifted first result; generating a third result by AND'ing each bit
of the second result with a respective bit in a predetermined constant;
generating a fourth result by right rotating the third result by a predeter-
mined number of bits; generating a fifth result by right rotating the fourth
result; generating a sixth result by OR'ing the fourth result with the sixth
result; generating a seventh result by AND'ing each bit respectively of the
sixth result with a respective bit of a predetermined constant whereby the
new cyclic redundant check character is generated.
According to another broad aspect of the present invention, there
is provided in a computing system comprising an arithmetic and logic unit
(ALU), accumulator (AC), scratchpad memory (SPM), and register, coupled for
communicating with each other via an input-output (I/O) bus, apparatus for
generating a cyclic redundant check character comprising: means for storing
first coded signals in said SPM representing a cyclic redundant check
character; means for loading in said AC second coded signals representing
~,. ~".
new data for which a cyclic redundant check character is to be generated; a
control store comprising: first instruction means for controlling said ALU
to exclusive OR said first coded signals with said second coded signals to
generate a first result; second instruction means for controlling said AC to
left shift said first result by a predetermined number of bits; third instruc-
tion means for controlling said ALU to exclusive OR said first result with
said left shifted first result ~o generate a second result; fourth instruc-
tion means for controlling said ALU to AND said second result with a pre-
determined constant to generate a third result; fifth instruction means for
controlling said AC to right rotate said third result by a predetermined
number of bit positions to generate a fourth result; sixth instruction means
for controlling said AC to right rotate said fourth result by a predeter-
mined number of bit positions to generate a fifth result; seventh instruc-
tion means for controlling said ALU to OR said fourth result and said fifth
result to generate a sixth result; and eighth instruction means for control-
ling said ALU to AND said sixth result with a predetermined constant,
whereby a cyclic redundant check character is generated; and microprogram
control means for actuating said first through eighth instruction means in
the above-stated sequence after said first and second coded signals have
been stored in said first and second means, respectively, to generate a
cyclic redundant check character for said new data.
The invention will now be described in greater detail with refer-
ence to the accompanying drawings, in which:
Figure 1 is the prior art apparatus for generating and utilizing
the cyclic redundant check character of the invention;
Figure 2 are the states of the device of Figure 1 at various
times t;
Figure 3 is an intermediate arrangement of the bits utilized in
generating the cyclic redundant check character of the invention;
Figure 4 is a portion of a prior art computer system utilized to
practice the invention,
-5a-
1~i99~2Z
Figure 5 is the microprogram for microprogramming the control
store and the various state of the bit character as a result of each step;
Figure 6 shows the hardware for providing AND operations for an
alternate embodiment of the invention; and
Figure 7 shows the hardware for providing OR operations for an
alternate embodiment of the invention.
DESCRIPTION OF THE PREFERRED EMBODIMENT OF THE INVENTION
General
Since the invention performs the same functions of generating a
cyclic redundant check character and utilizing it as do prior
-5b-
~W90Z2
art apparatus added to a computer ~ystem, but does no~ require
any additional hardware to be ~dded to a compûter ~ystem other
than that already present in most prior art computer systems,
it would be helpful ln understandlng the invention, to further
discu~s in greater det~il the prior art hardware ~peclfically
utilized for generating the cyclic redundant check character~
Moreover, it i~ desirable to discuss the prior art hardware
existing in most computer 8y8temg such as the arithmetic and
logic unit (ALU), accumulator and 8cratchpad memory which does
not 8;enerate or utilize a cyclic redundant character, but c~n
be modified by microprogramming the control store or ROM, to
control th.e ALU, accumulator altd gcratchpad memory so that
these elements cooperate and function with each other to
generate and utilize the cyclic redundant check character for
error control.
Referring, therefore, to Figure 1 there is shown prior art
shift: registers 101, 102 and 103. Shift register 103 stores
and ~;hifts a unit of data comprised of 6 bits do through d5
(It ~hould be understood that any number of bits may be utilized
as a unit of data). Shift register 101 stores half a unit of
data comprised of 3 bits CO through C2 whereas shift register 102
stores the other half of a unit of data comprised of 3 bits C3 - C5.
Between shift register 101 and 102 there is an exclusive OR circuit
B 104 coupling the X shift rc~gicter together; and between shift
regi3ters 102 and 103 there is an exclusive OR circui.t 104 coupling
7C~o
those X shift registers together. ~.oreover, the output of ex-
clusive OR circuit 105 is applied to exclusive OR circuit 104
and the data signal in the first bit position of shift register
101 is applied to exclusive OR circuit 105. The result of
serially shifting each bit from right to left through the vàrious
lO~Z~
bit positions of regi~ters 101, 102 at different times to ~ t6
t~ is shown ~n Figure 2. Referring to Figure 2 it will be seen that
at time to a bit CO iQ. stored at bit position O of shift register
101; at bit position 1, a bit Cl is stored; at bit position 2,
a bit C2 is stored; at bit position 3, a bit C3 is stored; at
bit position 4, a bit C4 is stored; whereas at bit position 5, a
bit ('5 is stored. At the next time interval tl all bits shift
to the left and in doing so certain of the bits are exclusive
OR'ed. Hence at time interval tl bit Cl is stored~ at b~t position
0; at. bit position 1, bit C2 is stored; at bit position 2 the ex-
clusive OR addition or the modulo 2 sum of bits 0, 3 and the first
bit of register 103 is stored resulting in the exclusive OR'ed
charn~ter CO, exclusive OR'ed to do which in turn is exclusive
OR'ed to C3; at bit position 3 the bit C4 i8 6tored; at bit
position 4 the bit C5 is stored; and at bit position 5 the
modulo 2 sum of bit CO and do is stored. At the next time
interval t:2 there is a shift of all bits to the left again
with certain of the bits being exclusive OR'ed as îndicated
in the column under t2. This procedure is repeated until at
time period t6 theshift registers 101 and 102 contain the cyclic
redundant check character shown in column t6 of Figure 2, which
is appended to the unit of data (in this example comprising 6
bits~ for which the cyclic redundant check character was generated.
The unit of data (i.e. the 6 bit character) and the concatenated
cyclic redundant check character are then stored for further use
or used immediately or transmitted to another portion of the
computer system or to another computer system. Upon receip~ of
this unit of data and its appended cyclic redundant check character,
the apparatu~ of Figure 1 would again be utilized in the same
manner and in the same sequence whereupon at time interval t6
~99~zz
there is a 0 result if all the bits of the received unit of
data are correct and have not been altered in the transmission
process. Hence the same apparatus is utilized both in generat-
ing and in utilizing the cyclic redundant check character. The
cyclic redundant check character in the diagram of Figure 2 is
the result of all the modulo 2 operations represented under
column t6. It can readily be appreciated that in order for this
system to be implemented, each transmitting and receiving
computer system must be equipped with the hardware of Figure 1.
This means additional cost in material and labor. However, since
most computer systems are equipped with prior art hardware as
shown on Figures 4, 5, 6 and 7, the instant invention produces
the same eyelie redundant cheek eharaeter as that produeed under
eolumn t6 by merely utilizing the prior art hardware of Figures
4, 5, 6 and 7 in a new and unobvious manner by generating firm-
ware via miero-programming the miero-program eontrol unit. The
term firmware is used herein as defined by Sippl and Sippl on
Page 186 of "Computer Dietionary and Handbook" i.e. logie eir-
euits in read-only memory that may be altered by the software
under eertain eireumstanees. This firmware then beeomes a
permanent additional funetion of the old eomputer system pro-
viding it with additional eapability it did not possess pre-
viously. Ge~erating firmware via miero-programming teehniques
is well known in the eomputer art and is deseribed in a book
entitled "Mieroprogramming Handbook" seeond edition, published
by Miero Data Corporation, 644 East Young Street, Santa Anna,
California and also a book entitled "Mieroprogramming:
Prineiples and Praetiees" by Samir S. Husson, published by
Prentiee-Hall Ine., Englewood Cliffs, New Jersey.
Referring to Figure 4, a portion of a prior art
B
105~9C~22
micro-programmed computer which is utilized by the invention
is shown. Moreover, such well known computer systems as the
Honeywell Series 60, and the IBM* Series 360 and 370 may be
utilized to practice the invention. Referring to Figure 4 there
is shown a micro-program control store
* Trade Mark
-8a-
~'099~ZZ
412 which for this particular computer is 16 bits wide,
although any other length may be utilized, and is expandable
to a maximum of 4,000 words. This amount of addressability
is sufficient to permit the practice of the instant inven-
tion. The output of the microprogram control store 412 isclocked into the microprogram instruction register 413 at
the leading edge of each clock cycle generated by central
clock 415. Additionally, the microprogram address counter
411 is advanced at the leading edge of every clock cycle to
indicate the new address. Thus, as one microinstruction is
stored in the microprogram instruction register 413 for
execution, the microprogram address counter 411 changes to
access the next microinstruction by incrementing by one.
When a branch command is executed, however, the increment
function of microprogram address counter 411 is inhibited by
techniques well known in the computer art and the microprogram
instruction register 413 is loaded with the output of the
microprogram address selector 410. As previously noted, the
output of control store 412 is stored in instruction register
413 for execution. The 3 high order bits of each microinstruc-
tion are coded to indicate the type of command and comprise
the op-code of the microinstruction. The op-code decoder 414
decodes the 3 high order bits of the instruction register and
applies the output to a time pulse distributor 416 which in
turn distributes control pulses to various hardware units to
control hardware operations. A more detailed description of
microprogrammed control units equivalent to microprogram con-
trol unit 401 described supra may be found in the above refer-
enced books. Moreover, typical microprogrammed control units
are disclosed in U.S. Patent 3,380,025 issued April 23, 1968;
and in U.S. Patent 3,955,180 issued May 4, 1976.
1~99(~ZZ
The unit denoted by the reference numeral 402 shows
in block diagram format the arithmetic logic unit 422, scratch-
pad memory 424 and accumulator 425 controlled by the control
signals generated by control unit 401. Information from the
accumulator, scratchpad memory, bus interface register 420 and
instruction register is applied to the arithmetic logic unit ALU
422 by means of multiplexer 421 which selects among others one
of these registers. The arithmetic and logic unit performs
arithmetic and logic operations depending on the coding of the
microinstruction in mocro-program instruction register 413 being
executed. The accumulator 425 is a 9-bit register which is
used for temporary storage of the output of the ALU 422.
Additionally, the contents of the accumulator can be right ro-
tated one bit position while left shift operations can be per-
formed by the ALU 422. (Arithmetic logic units and accumulators
are well known in the prior art, some typical ones being disclos-
ed in U.S. Patents 3,404,378 issued on 10/1/68 and in 3,238,508
issued 3/1/66. Also multiplexers are well known and commercially
available from such companies as Texas Instruments Inc., of
20 Dallas, Texas. See pages 9-339 through 9-364 of the Integrated
Circuits Catalog for Design Engineers, published by Texas
Instruments of Dallas, Texas for description and availability of
data selectors, and data multiplexers). The scratchpad memory
424 of the prior art system being described herein is comprised
of 256 9-bit words for storing data, status commands, etc.,
although any other word size or quantity may be utilized. Typi-
cal scratchpad memories are disclosed in U.S. Patents 3,248,708
issued 4/26/66 and in 3,351,909 issued 11/7/67. Data may be
written into scratchpad memory 424 from the ALU operand multi-
plexer 421 which permits any visible register to serve as an
input local
_-~
~'099Q2Z
register. Data out from the scratchpad memory 424 is applied
to the ALU operand multiplexer 421. An 8 bit SPM address counter
423 is loaded with the result of an ALU operation and can be
incremented at each clock cycle. The output of the SPM address
counter is applied to the ALU operand multiplexer 421; moreover,
SPM address counter 426 is also utilized to address the scratch-
pad memory 424. The central clock 415 is an 8 MHZ crystal
oscillator which is divided to obtain a 250ns clock cycle. The
clock cycles developed from the central clock 415 are then dis-
tributed to the various elements of Figure 4. Crystal oscil-
lators for providing clock cycles are well known in the prior art.
(Typical computer timing and control systems are shown in U.S.
Patents 3,254,329 issued 5/31/66 and in U.S. Patent 3,417,379
issued 12/17/68).
Detailed Description and Operation of the Invention
Referring now to Figure 3 and Figure 5, a detailed
description and operation of the invention is presented. It
should be noted that one of the objects of the invention is to
obtain the results in column t6 of Figure 2 without utilizing
the additional prior art hardware of Figure 1. Aceordingly,
one of the first objectives of the firmware eontrol of the
invention is to arrange the various bits of a word being
reeeived in a definite pattern relative to the bits of the pre- -
vious word reeeived. Inspeetion of eolumn t6 shows that the
first bit in eaeh row of that column has a partieular sequence
whieh is also shown in row 1, of Figure 3. Similarly, the
sequenee of bits in eolumns 2, 3 and 4 within eolumn t6 f
Figure 2 are shown in rows 2, 3 and 4 respeetively of Figure 3.
By exelusive OR'ing the data eontained in the bit positions of
various rows of Figure 3, the result desired is obtained. How
--11--
, ~
1~99C12Z
this is performed by the firmware is shown in Figure 5.
Figure 5 illustrates the micro-program of the inven-
tion and shows the results of each step. Referring now once
again to Figure 5, row ~ shows the old residue in scratchpad
memory 424 as a result of the previous manipulation in obtaining
the cyclic redundant check character. Row/~ shows the new data
which has been received in the accumulator 425. On step number 1,
the old residue is exclusive OR'ed bit by bit by the arithmetic
and logic unit ALU with the new data in the arithmetic and logic
unit ALU 422 and the result is temporarily stored in the
accumulator. In step l(a), the results stored in the accumu-
lator 425 are transferred and stored in a predetermined location
in scratchpad memory 424; moreover the result in the accumulator
is also left shifted 3 bits so that zeroes occupy the first 3 bit
positions of the accumulator. In step number 3 the left shifted
result of the accumulator is exclusive OR'ed with the previously
stored results of step l(a) in scratchpad memory and temporarily
stored in the accumulator. Once again the ALU is utilized for
this operation. In step number 4 each bit in the accumulator
is AND'ed with one bit of the constant K=000111111. This oper-
ation is performed in the ALU 422. However, an alternative
embodiment is shown in Figure 6. Three inputs are applied to
each AND gate 601-609. One input for each AND gate is one digit
respectively of the constant K=000111111; another input of each
AND gate is the signal stored in a respective bit position of
the accumulator; finally a clock pulse is applied as another
input to each AND gate 601-609 to enable each gate; thus giving
the results at
-12-
iwsc~
the output of each AND gate. This result is temporarily
stored in the accumulator. In step number 5, the accumu-
lator is right rotated 3 bits and the result saved in a
predetermined address in the scratchpad memory 424.
Another right rotation of the accumulator is performed in
step 6. It should be noted that the first 3 bit positions
of the accumulator store a quantity which is meaningless
in step 6, and is denoted in Figure 5 by the symbol X. In
step number 7, the right rotated result stored in the accumu-
lator is OR'ed with the value saved in scratchpad memory424 in step 5. This is done in the preferred embodime~t by
the ALU 422. An alternative apparatus for doing this is
shown on Figure 7. To each OR gate 701-709 there is applied
2 inputs, one input on each OR gate from a respective bit of
the resulting bits of data saved in the scratchpad memory 424
and another input on each gate respectively from a respective
bit of the resulting bits of data stored in the accumulator
425. Accordingly, on OR gates 701, 702 and 703 a meaningless
output signal denoted by the letter X is obtained at each
output terminal. On OR gates 704-709 where a respective input
is OR'ed with zero, the output of each gate is merely the
other input of the respective OR gate. These outputs of OR
gates 701-709 are temporarily stored in accumulator 425. In
step number 8, each bit of the accumulator is once again
AND'ed with each bit respectively of the constant K=000111111
as previously described supra. Finally, step number 9 stores
the result of the accumulator in a predetermined position in
scratchpad memory as a residue and is the cyclic redundant
check character for the word just received. It should be
noted by comparing the last row of Figure 5 with the last
column t6 of Figure 2 that the results are identical. This
has been accomplished by utilizing existing hardware in
the computer
-13-
1~99Q22
system by micro-programming the micro-programmed control unit
to produce the firmware herein. Accordingly, not only has the
invention produced a new combination and a new use of an old
machine but a synergistic result as well, since the computer
system has been given additional capability by utilizing the
old elements of the computer to perform in a manner which is
greater than the sum of its parts i.e. do something the old
elements could not do singly or in combination.
-14-
B
