 |
Description  |
|
|
BACKGROUND TO THE INVENTION
The invention relates to a data processing system based on a 100%
redundancy four-symbol code-word code having both single-symbol error
correctability and plural error mendability with respect to at least two
symbols in one code word coexistently, said system having:
a. a decoder stage having an input for receiving code words and to
therefrom deriving two-symbol data words;
b. a processor stage fed by said decoder stage to process said data words
for therefrom developing memory addresses and further data words;
c. an encoding stage having multiple encoder modules for receiving
intendedly identical versions of a selection of said data words and for in
respective encoder modules encoding unto respective different code
symbols:
d. a memory stage having multiple memory modules each fed by a respective
one of said encoder modules for under control of said memory addresses
collectively writing and reading all code symbols of an associated code
word;
e. feedback means fed by said memory modules for retrocoupling any code
word so read to said decoder stage. U.S. Pat. No. 4,512,020 (PHN 10155,
code 81), especially FIG. 24 thereof describes a four-module system that
allows one module to completely fail without rendering the overall system
inoperative. Symbols of a code word have a uniform length of a plurality
of bits, in the reference of four bits. Correctible means that an
arbitrary disturbance can be determined quantitatively and thereupon
restored. So, both the questions as "where" the disturbance occurs and
"what" the disturbance is, are answered. On the level of a single bit
these two notions are identical. On the level of a plural-bit symbol,
pointing the disturbed symbol is only the first step in realizing the
correction. On the other hand, mendable is understood to mean that the
effect of an error can be made inconsequential. In addition to full
correction, this includes the possibility for declaring one or more
particular symbols invalid or "erased" so that they would have no bearing
for retrieving the code word's data content. Of course, such erasure
renders the remainder of the code word less robust against further
disturbances. On a higher level, mendability may on the level of the code
proper also be restricted to detecting-only of the error. Then, the
measures effectively taken could be a retry of the operation that would
make a soft error presumedly invisible, a recourse to a higher-level
authority such as a background memory, or just the being on one's guard as
to the incorrectness encountered.
SUMMARY OF THE INVENTION
The above-referred (4,2) code conventionally has been mapped on a 4-module
system, so that any symbol error corresponds to a module error and vice
versa. The hardware has become attractive for use in such secure systems
as telephone exchange controls. Now, it is among other things an object of
the present invention to use the modular hardware, devised for the above
(4,2) system and comparable systems, for other configurations wherein the
direct correspondence between module and symbol has been given up while,
either in an extended system, or in a more limited configuration, still
realizing excellent cost vs effectivity results. An additional advantage
of using standard hardware would be that development costs are now shared
amongst a larger number of copies of such hardware, thereby effectively
lowering the overall price tag.
According to one of its aspects, the invention provides a data processing
system according to the preamble, and characterized in that said data
processing system comprises at least one data processing unit wherein any
said unit has more than one but less than four different active encoder
modules, fed in parallel by its local processor module for collectively
processing one single of said versions, for in respective memory modules
of the data processing unit storing respective disjunct symbols of the
data word version developed in the latter data processing unit.
Breakdown or malfunctioning of a single data processing module may now have
more serious effects than according to the state of the art. On the other
hand, the invention's robustness against malfunction on the code symbol
level compares with the state of the art, while offering appreciable
configuration flexibility, as explained infra.
Now, whereas the above deals with an (n,k)=(4,2) code, similar
considerations apply to other codes, such as, in particular, but not
limited to (6,4), (8,4) and (8,5) codes. These codes, due to a greater
number of symbols per word, either would have a greater degree of
protection, or a higher efficiency (=lower fractional redundancy) or allow
for shorter symbols (divide the data bits among a greater number of
individual symbols) or any advantageous mixture thereof, such as the
skilled art worker would readily recognize. Nevertheless, the same
advantages as regards the (4, 2) code would be realized. The skilled art
worker would recognize maximum values of n, k as dependent on the symbol's
bit length. In consequence, according to an even broader aspect of the
invention, it provides a data processing system based on a code having
n-symbol code words at a k-symbol information content per code word,
wherein n-k.gtoreq.2 and k.gtoreq.2 and having at least single-symbol
error correctibility and plural error mendability with respect to at least
two symbols in one code word coexistently, said system having:
a. a decoder stage having an input for receiving code words and to
therefrom deriving k-symbol data words; b. a processor stage fed by said
decoder stage to process any word received for therefrom developing memory
addresses and further data words;
c. an encoding stage having multiple encoder modules for receiving
intendedly identical versions of each of a selection of said further data
words for in respective encoder modules encoding unto respective different
code symbols of the associated code word;
d. a memory stage having multiple memory modules each fed by a respective
one of said encoder modules for under control of an associated one of said
memory addresses collectively writing and reading all code words of said
associated code word;
e. feedback means fed by said memory modules for retrocoupling any code
word so read to said decoder stage,
characterized in that said data processing system comprises at least two
data processing units wherein any said unit has more than one but less
than n different encoder modules, fed in parallel by its local processor
module for collectively processing one single of said versions, for in
respective memory modules of the data processing unit storing respective
disjunct symbols of the data word version developed in the latter data
processing unit.
By itself, multi-encoder modules have been described in U.S. Pat. No.
4,633,472 (PHN 10.474). There, in a standard 4,2 system according to the
first-cited art, each unit has a standard encoder module to generate a
code symbol from the data word produced locally for subsequent storage in
a standard local memory module. Moreover, specifically for I/O purposes, a
second memory module is present that is provided with a second encoder
module and complementary decoder module. However, the so-encoded symbols
are used for storage in the second memory module, and are not used in
combination with code symbols read out from the first memory module, for
collective decoding thereof. So, this particular reference has the two
encoder modules operating mutually asynchronously on the data word level.
According to the present invention, the plural encoder modules do not
represent alternative possibilities for respective alternate
functionalities, but function as based on a unitary data word content,
that is, either on a single data word, or on two (or more) data words that
should in theory or intendedly be identical. When using the (4, 2) code,
at least on the level of the data processing unit, the error mending
capability is inferior to that of a full (4,2) system.
According to a further aspect of the invention, it provides a data
processing system having a single processing unit that has three different
encoder modules for so storing a 50% redundant code word at an error
protection capability at least equal to that of an (12,8,3) Hamming code.
As explained hereinafter, flexible mendability is substantially improved
in this way, with respect to the (12,8,3) Hamming code, that has the same
redundancy.
According to a still further aspect of the invention, it provides a data
processing system having two processing units that each have two unique
encoder modules each feeding an associated memory module for having said
system so storing a 100% redundant code word for rendering correctable any
double bit error pattern, for under presence of a first erased symbol
rendering detectible any error in a second symbol error, or alternatively
rendering correctable any single bit error in such second symbol, and for
rendering retrievable from any two code symbols the associated data word.
In this way, on the symbol level the same protection is produced as that
of a (4,2) system; on a unit level, the protection is less, which is
mitigated by decreased processor costs.
According to a still further aspect of the invention, it provides a data
processing system having four processing units that each have two encoder
modules that are unique among the odd or among the even processing units,
respectively, each feeding an associated memory module for in said system
storing two parallel versions of said 100% redundant code word, each such
code word deriving one respective code symbol from each one of said
processing units and being backfeedable to any of said processing units,
so that upon any single-unit disability still any code word is flawlessly
stored in the collective memory modules. In this way, a fourfold system is
realized, that moreover, has extensively improved error protection with
respect to the quasi fourfold (4,2) system.
According to a still further aspect of the invention it provides an
application of the (4,2) system in that it provides a system wherein said
data processing system comprises three data processing units that each
have one unique encoder module, fed in parallel by its local processor
module for collectively producing three code symbols as based upon a 50%
emulated data word version, any processing unit having a decoder module
for receiving three code symbols in parallel while also receiving a dummy
code word symbol and outputting a dummy data word symbol. Through use of
dummy symbols, in this way an elementary (3,1) system is realized as based
on the same hardware as the (4,2) standard system, with about as good an
error protection capability as the best (3,1) systems that are considered
feasible.
In addition to the various representations described herein that are
founded on the (4,2) system, similar versions could be built with respect
to other (n,k) systems that have n-k.gtoreq.2, k>2 or n>4, and in addition
to the straight symbol correctability (such as by Reed-Solomon codes)
other, extended error correction capability, due to their additional error
protection on the bit-non-symbol level. Effectively, this additional error
protection is realizeable in that the symbol number is relatively small
with respect to the number that could be used for the actual symbol length
counted in bits. For example, a (6, 4) code could be used as one unit
having five encoder modules, or as three units each having two encoder
modules, or as six units each having two encoder modules. An (8, 4) code
could be used as one unit having six or seven encoder modules, or two
units each having four encoder modules, or four units each having two
encoder modules. The (6, 4) code, by comparison with FIG. 5, infra, could
have five units each with one encoder module and three dummy symbols. The
(8, 4) code could have seven units each with one encoder module and three
dummy symbols. Many other realizations would become apparent to the worker
in (n, k) system technology. Generally, an (n, k) code can be used to
build various (m, I) systems, wherein I<m<n and 1.ltoreq.I.ltoreq.k.
BRIEF DESCRIPTION OF THE FIGURES
The invention will hereinafter be explained in detail in and by the
appended Figures that show various preferred embodiments, wherein
FIG. 1 shows a conventional (4,2) system;
FIG. 2 shows the use of the (4,2) code in a single-unit system;
FIG. 3 shows the use of the (4,2) code in a two-unit system;
FIG. 4 shows the use of the (4,2) code in a (4,1) system;
FIG. 5 shows the use of the (4,2) code in a three-unit system.
DESCRIPTION OF PREFERRED EMBODIMENTS
In computer systems, error correcting codes are often used to improve the
reliability. An example is the use of the Hamming code to correct single
bit errors in the data received from memory.
However a general approach is the (n,k)-concept computer. This approach
gives the opportunity to choose the ratio between processor redundancy and
memory redundancy. This means that the reliability versus costs can be
optimized by choosing the appropriate values for n and k.
For instance if the values n=3 and k=1 are chosen a TMR (Three Module
Redundancy) system is obtained. In this case all hardware is tripled. If
the values n=4 and k=2 are chosen a (4,2)-concept system is obtained. In
this case the processor logic is fourfold and the memory is only doubled.
The most expensive part of the system is often the memory. Therefore the
costs of a (4,2)-concept computer can be lower than the costs of a
(3,1)-concept computer.
In an (n,k)-concept computer an error correcting/detecting code is used.
This code is called the (n,k)-code. For the traditional TMR system a
replication code is used. This code is not optimal. For the (4,2)-concept
the (4,2) code is used. The (4,2)-concept as well as the properties of the
(4,2) code have been published, see the first-mentioned reference.
The (4,2) code can also be used efficiently in other systems. The (4,2)
code is used generally hereinafter. It is shown that a (4,2) code can be
used instead of a Hamming code in a single unit system. Also, the
advantages of the (4,2) code in a (2,1)-concept (doubled) system are
discussed. It is shown that the (4,2) code can also be used in a
(3,1)-concept computer. A short discussion on the use of the (4,2)-concept
computer is presented.
The method described herein can be generalized to the use of the
combination of an (n,k)-code and (m,l)-concept system, if
1.ltoreq.m.ltoreq.n and 1.ltoreq.l.ltoreq.k. However depending on the
values of n,k,m and l different characteristics show up. An example
illustrates the method.
In the following, first a short description of a (4,2)-concept computer for
four-bit symbols is presented. Hereafter an overview of the properties of
the (4,2) code is given. The (4,2)-concept computer consits of four units
(see FIG. 1). Each unit, such as 20, comprises a chain of a four symbol
in, two symbol out decoder module 22, a processor module 24, an encoder
module 26 and a memory module 28. The data input of the memory module is
fed by the encoder module. The address input 30 need not be fed by the
encoder module as this would only represent shuffling among the memory
addresses, and, moreover, would diminish the available address range. For
brevity, no control paths and no mutual synchronization among the four
units have been shown. The assumption made in an (n,k)-concept computer is
that the n modules are designed to run synchronous and deterministic. In
the following only the processor/memory communication is discussed. The
connection with external systems is not discussed.
During a write each processor writes its data through the encoder into the
memory. The encoders differ in each module which has been indicated by
their different labeling G0, G1, G2, G3, respectively. In this way the 8
bits of information are encoded in a 16 bit code word. However each unit
only stores 4 bits (a code symbol) of this code word. When the processors
read the information back from the memory the four symbols are received in
each unit by the decoder. The decoder will generate the original
information for the processor in each unit if the amount of errors does
not exceed a certain maximum. In practice, however, each unit could have
identical hardware for in effect realizing all four different encoder
modules, inasmuch as this would only represent a slight addition to the
silicon area, which could be more than outweighted by the advantage of a
fourfold increase in the number of mutually identically circuits (=units)
that were to be manufactured.
The amount of errors that can be corrected is given by the properties of
the (4,2) code. In the following the most important properties of the
(4,2) code are listed. Next, these properties will determine how the (4,2)
code may be used in other systems. Now, these properties, for four-bit
symbols, are as follows:
1. correction of any arbitrary single-symbol error;
2. correction of any double-bit error pattern;
3. if one symbol is erased another symbol error can be detected;
4. if one symbol is erased a single-bit error can be corrected;
5. from any two symbols the original information can be retrieved;
6. two symbols are the original information symbols.
Property 3 follows from the observation that the minimum symbol weight of a
code word (=number of non-zero code symbols) with one erased symbol is
equal to 2.
THE USE OF THE (4,2) CODE IN A SINGLE-UNIT SYSTEM
The (4,2) code can be used in a single-unit system as a replacement of a
(12,8,3) Hamming code. The system according to the invention is shown in
FIG. 2, which has a four-symbol decoder 40 (of which one symbol input is
not used), a processor module 42, three different encoder modules G0, G1,
G2 each feeding an associated memory module 44, 46, 48. These are again
addressed by processor module 42. With respect to the Hamming code system,
no extra costs are involved: the amount or memory is the same. However the
(4,2) code implementation offers more. In the following a short
explanation of the implementation of a (4,2) code in a single system is
given.
During a write the 8 bit information word is encoded in three different
ways by the encoders G0, G1 and G2. This results in three 4-bit code
symbols. Each of them is written into an associated memory module.
Generally, within the unit, the various memory modules may be part of (a
bank or block of) a larger memory unit. During a read cycle the three code
symbols are received by the decoder. The decoder is in an erasure mode. It
erases the fourth symbol that had not been stored in memory. The decoder
decodes the 12-bit code word into an 8-bit information word that is
offered to the processor.
The following error detection/correction capabilities are available in this
way:
single bit error correction or,
single symbol error detection.
The single bit error correction follows from property 4. With a Hamming
code exactly the same result would have been obtained so far. However if a
bit error appears to be a hard error it is easy to switch the decoder in
single mode so that only two 4-bit symbols determine the output of the
decoder. In this way only 8 bits determine the output of the decoder
instead of 12 bits of which one is faulty. So the probability that the
output is erroneous due to another bit error is reduced to 8/11 of the
original probability.
The fact that the symbol weight of a code word with one erased symbol is at
least two, leads to the conclusion that it is also possible to detect
single symbol errors (property 3). This can be useful if the memory is
designed as memory banks of 4 bits width each. The failure of such a bank
can be detected.
The solution with the (4,2) code is flexible in the sense that the
designer/user of the system can maximize the reliability of the system by
chosing the proper method. Note that this entirely depends on the
strategy. The hardware is exactly the same.
THE USE OF THE (4,2)-CODE IN THE (2,1)-CONCEPT
FIG. 3 shows how a (4,2) code can advantageously be used in a doubled
system. The left hand unit has decoder module 60, processor module 62,
address bus 64, encoder modules G3,G2 feeding memory modules M3,M2,
respectively. The right hand unit is structurally identical, except for
encoder modules G1,G0, that feed memory modules M1,M0, respectively. Of
course, all memory modules may be structurally identical. Now, the same
encoders and decoders are used in the doubled system as in the
(4,2)-concept computer. Only the error control differs, since the same
type of error will not result in the same action. The advantage of the
(4,2) code used in a doubled system is that the designer or user can adapt
its fault-handling mechanism depending on the relation between the type of
error and the type of fault or system degradability. An alternative for
the (4,2) code is a (2,1)-code. However the (4,2) code is optimal because
it is used as a (2,1)-code. In the | | |
