Note: Descriptions are shown in the official language in which they were submitted.
17 Reference to Related Patent
18 U. S. Patent 3,689,899 issued to P. A. Franaszek and
19 assigned to the same assignee, teaches a class of codes having
desirable density and run length properties. With the codes
21 described therein, the length of the word to be encoded or
22 decoded varies for different data patterns. For each successive
23 word in a sequence, a decision must be made as to the number of
24 bits in the word, the word must be framed, and the appropriate
number of bits must be encoded or decoded
26 Background of the Invention
27 Field of the Invention
28 This invention relates to a novel method of encoding and
29 decoding data.
SA973024
.
~ - " . ~ .
' ' ' ' : . . ' ' ~ ': '
- \
1081849
1 Description of Prior Art
It is known that run length limited codes employing varia-
ble length words are more efficient than those using fixed
length words. However, in prior art systems variable lenqth
words generally require framing at proper places to demarcate
respective code words. In one known system, special marker
bits are used at the beginning of each word in conjunction with
a table lookup procedure. This arrangement is relatively slow
and costly. Also, when word framing is used, faulty bit detect-
10 ion tends to propagate a framing error for succeeding bit
groups. In such case, a statistical probability approach is
employed, but this approach has problems of regaining synchroni-
zation and also of operating within the run length limited
constraints.
It would be advantageous to use a run length limited var-
iable length coding technique in which framing decisions are
not required and translation of input data may be accomplsihed
with incomplete words.
Definitions
The codes addressed herein are defined by specifying a set
of allowable sequences of coded bits ~code words), each code
word corresponding to a unique sequence of data bits.
A code is described as fixed-rate if for every correspond- -
ing pair, consisting of a data word of length m bits and code -
word of length n bits, the ratio of m to n is fixed.
A code is described as having fixed length words if the
lengths of all code words are the same, and variable length
words otherwise. In variable word length codes, only a prede-
termined plurality of bit patterns of differing lengths are
30 valid code words.
Encoding is the process of operating on a sequence of one
or more data words so as to produce the corresponding sequence
- . .. .
~" 1081849
1 of code words. Decoding is the inverse process, i.e , that of
operating on a sequence of one or more code words so as to pro-
duce the corresponding sequence of data words.
Summary of the Invention
.
An object of the invention is to provide an encoding and
decoding scheme employing variable word-length, fixed-rate data
codes that do not require framing of entire words during the
encoding or decoding process.
Another object of this invention is to provide a run-
length-limited variable-word-length data code in which the data
is encoded and decoded bit-by-bit instead of on a word-by-word
basis, therefore requiring relatively simpler logic.
In accordance with this invention, methods of encoding and
decoding variable-word-length codes on a sequential basis are
provided, such that each input of a group of (m) bits is trans-
lated into a group of (n) bits, where (m) and (n) are fixed in-
tegers whose ratio depends on the rate of the code. Code words
of the input sequence are not framed, and translation may be
accomplished on incomplete words.
For encoding or decoding in which word boundaries cannot
be recognized by examining a limited amount of data, auxiliary
state variables must be used to account for the position in the
shift register of a word boundary. These auxiliary variables
.
can be implemented as a shift register, or as a resettable
counter, or as any other suitable sequential circuit.
In a specific embodiment of encoding, a first three-bit
shift register and a second two-bit shift register or counter
are employed, the second shift register or counter changing its
state according to the data pattern. The bits that are stored
in the first shift register are encoded on a bit-by-bit basis,
SA9-73-024 -3-
' ' ' ~' - ''
~ ,- . -......................... ,
-
10818~9
1 and processing of the data is not dependent on a variable number
2 of bits that are shifted into the first register.
3 The stored information in the encoder is (a) the values of
4 the three most recent bits of the series of input bits; and (b) -
the position of the boundary between words, if the three stored
6 input bits belong to more than one word.
7 A specific embodiment of decoding corresponding to the above
8 encoder consists of an eight-bit shift register and combinational
9 logic by means of which data is decoded on a bit-by-bit basis
from the contents of the shift register.
11 Brief DescriPtion of the Drawing
12 The invention will be described in greater detail with
13 reference to the drawing in which:
14 FIGURE 1 is a code table showing correspondence between
code words and data patterns for a run-length-limited code of
16 variable word length in which the coded sequences have minimum
1~ and maximum runs of zeros between ones of length two and seven,
18 respectively;
19 FIGURE 2 is a schematic representation of a sequential en-
coder used for generating a variable-word-length code, in accord-
21 ance with this invention;
22 FIGURE 3 is a logic diagram illustrating an embodiment of
23 the sequential encoder of FIG. 2 for the code described in FIG. l;
24 FIGURE 4 is a timing chart showing the relationship between
various signals in the encoder;
26 FIGURE S is a tabular illustration of an example of the
27 encoding of a data pattern by the sequential encoder of FIG. 3
28 in accordance with this invention;
29 FIGURE 6 is a schematic representation of a sequential
decoder used for detecting the code generated by the sequential
31 encoder of FIG. 2;
SA973024 -4-
,
- - ~- , ~ . . . .
- . , . . ;
~ 1081849
1 FIGURE 7 is a logic diagram of an embodiment of the se-
2 quential decoder of FIG. 5 for the code described in IG. 1;
3 FIGURE 8 is a timing chart showing the relationships between
4 various signals in the decoder; and
FIGURE 9 is a tabular illustration of an example of decod-
6 ing the data by the sequential decoder of FIG. 7 in accordance
7 with this invention.
8 Similar numerals refer to similar elements throughout the
9 drawing.
Description o the Preferred Embodiment
11 FIGURE 1 sets forth a run-length-limited code with variable
12 word length of the kind contained in the related patent 3,689,899
. .
13 cited above. In this code, each code word consists of twice as
14 many bits as the'corresponding data word. While the code is a
variable word length code, it is a constant rate code in that
16 two codod bits correspond to each data bit.
17 With reference to FIGS. 2 and 3, a sequential encoder that ~s
~. . .
~18~ used for en¢oding data in variable length words according to the
19 code described in FIG. 1 comprises a first shift register 15 that
includes storage circuits 14, 16, and 18, a second shift register
21 21~that includes storage circuits 20 and 22, and logic circuits
22 23 which contain no storage elements.
l 23 In FIGS. 2 and 3, the variable p is a "l" when the bit
;1 24 stored in storage circuit 14 is the last bit of a word. A "1"
,l,,,'~ 25 is stored in storage circuit 20 when storage circuit 16 contains
fi 26 the last bit of a word, and a ~lu is stored in.storage circuit
j, ,
27 22 w,hen storage circuit 18 contains the last bit of a word.
28 In FIG. 3, each storage circuit is shown as having two flip-
29 flops, ~-1) and (-2), respectively. For encoding, a clock signal
(generation not shown) is used which runs at the rate of one cycle
.
~ 1 .
.
SA973024 -5-
.
.
:
~ .
r
^~ 108~49
1 for each data bit to be encoded. During successive clock
2 cycles, serial binary data derived from a memory store (not ~;
3 shown) are applied to lead 10 at the input of shift register
4 15. During each positive clock phase, the value of the in-
put data bit on lead 10 is transferred to the first latch
6 14-1. If the binary data is a "one", for example, the
7 latch is set and stores that information. ``
8 Simultaneously with the entering of a data bit into
g latch 14-1, the contents of latches 14-2 and 16-2 are tran-
sferred to latches 16-1 and 18-1, respectively. During the
11 negative clock phase,~the data bit values stored in the
12 latches with suffix 1 are set into the corresponding latches
13 with suffix 2, thus completing the shift cycle.
14 'rhe operation of shift register 21 is similar, except
that the input to the first latch 20-1 is the variable p,
16 derived from the contents of shift registers 15 and 21. A
17 ~ombinatorial logic circuit 23 senses the arrangement of
18 binary data and determines whether signal p at the output
19 line 25 will be high or low. The signal p will be high if
(1) all storage circuits 14 through 22 are in the zero or
21 low state; or (2) storage circuit 18 is at zero and storage
22 circuit 16 stores a binary one; or (3) if storage circuits
23 16 and 18 register a binary one and storage circuit 20 is a
24 zero. If any of these three conditions exist, then p will
. . _ .
;~ 25 be high, and will cause a binary one to be set in latch 20-
26 1 during the positive clock phase. Expressed logically, p
27 = abcqr + ab + abr where c,b,a,r and q correspond to the
28 outputs of latches 14, 16, 18, 20 and 22 respectively. ~ith
29 reference to FIG. 3, p is generatèd by AND circuits 24, 26,
3-0 28, and OR circuit 42. The inputs to 24, 26, and 28 are
31 taken from the suffix-2 latches of shift registers 15 and
32 21, which are unchanged during the positive clock phase.
SA9i3024 -6-
.. ,. . .. , ..... ... .. ,. :
~OB1~49
The variables to and tl represent the values of encoded
2 data bits, to being gated to the coded output sequence
3 during the negative clock phase by AND circuit 36 and OR
4 circuit 40, and tl being gated to the coded output sequence
during the positive clock phase by AND circuit 38 and OR
6 circuit 40. The variable to is ~enerated by ~ND circuits
7 30 and 32 and OR circuit 44. The inputs to 30 and 32 are
8 taken from the suffix-l latches of shift registers 15 and
9 21, which are unchanged during the negative clock phase.
The variable tl is generated by AND circuit 34. The inputs
11 to 34 are taken from the suffix-2 latches of shift registers
12 15 and 21, which are unchanged during the positive clock
13 phase. Using the same notation as above, : to = abcq
14 + abq and tl = br.
FIGURE 4 is a chart with explanatory legends showing
16 the timing of various signals.
17 , FIGURE 5 illustrates encoding example employing the
18 code of FIG. 1. Two bits are encoded for each input bit.
19 The outputs to and tl (see ~IGS. 2 and 3) are respectively,
the first and second encoded bits corresponding to the
21 particular input data bit contained in storage circuit 18.
22 The arrows from left to right show the progression of the
23 first bit of data (emphasized) from input, to generation of
24, the corresponding pair of encoded bits. The dashed lines
show the division between words in both input and encoded
26 data sequences.
27 The encoding sequence is as follows: Initially, all
28 latches of shift registers 15 and 21 are reset to the zero
29 state (resetins losic not shown). Serial data is entered
into shift register 15 in synchronism with the clock. For
31 the first t~o clock periods of a sequence, the coded data
3~ ou.puts, to and tl, are ianored. ~fter the first three
S~.973024 ~: 7
~ `
,
--~ 108~4g
1 data bits have been entered into shift register 15, the
2 coded data outputs are used to generate the encoded data ~
3 stream, two coded bits being generated for each input data ~ -
4 bit. Following the entry of the last data bit of the
sequence, two "dummy" bits are entered to complete the
6 encoding process.
7 With reference to FIGS. 6 and 7, a sequential decoder
8 that is used for.decoding variable length code words that
9 have been generated according to the code table of ~IG. 1
comprises a shift register 53 that includes storage circuits
11 52,54,56,58,60,62,64 and 66, and logic circuits 67 which
12 contain no storage elements. No auxiliary state variables
13 are required for decoding the code set forth in FIGURE 1.
14 In FIG. 7, each storage circuit is shown as two flip-
flops, (-1) and (-2), respectively. For decoding, a first
16 clock si~nal 48 (generation not shown) is used, which runs
17 at the rate of one cycle for each coded bit. Flip-flop 68
18 is a frequency divider driven by clock signal 48 to produce
19 a second clock signal 49 which has a rate of one cycle for
each decoded data bit. During successive cycles of clock
21 48, serial coded data from a storage medium (not shown) are
22 applied to lead 50 at the input of shift register 53. Dur-
23 ing each positive phase of clock 48, the value of the coded
24 bit on lead 50 is transferred to the first latch 52-1.
, .
25- Simultaneously with the entering of a coded bit into latch
26 52-1, the contents of latches 52-2, 54-2, 56-2, 58-2, 60-2,
27 62-2, and 64-2 are transferred to latches 54-1, 56-I, 58-1, -
28 60-1, 62-1, 64-1 and 66-1, respectively. During the
29 negative phase of clock 48, the coded bit values stored in
latches with suffix 1 are set into the corresponding latches
31 with suffix 2, thus completing a shift cycle.
32 The combinatorial logic circuit 67 is used to determine
SA973024 \ -~-
'.
3 ~.0~18~9
3 the val~es of decoded data bits from the contents of shift
2 register 53. AND circuits 72, 74, and 76 and OR circuit 78
3 are used to generate a decoded data bit for each pair of
4 coded bits entered. If the digits contained in latches
52-66 are h-a respectively, the output t of OR 78 is expres-
sed by : t = c + eh + bdf + af.
,:.
. , ' .
.:
.' .
SA973024 -8a-
~ . ~ ' ' . .
~_ , .: .
1081~49
1 The outputs of 78 and inverter 80 are valid whenever an even
2 number of coded bits have been entered into shift register 53.
3 Latch 70 is set to the value of the decoded bit at the appropri-
4 ate times (clock 48 and clock 49 both positive).
With reference to FIG. 7, in decoding the code of FIG. 1,
6 word endings in shift reqister 53 are recognized by the logic 67.
7 A word ending is recognizable after any even number of encoded
8 bits has been entered into the shift register. The encoded pattern
9 in the shift register at the end of a word is
0 0 0 1
11 or
12 0 0 1 0
13 in storage circuits
14 52,54,56,58
or
16 56,58,60,62
17 or
18 60,62,64,66.
19 FIG. 8 is a chart with explanatory legends showing the timing
of the various signals for decoding.
21 FIG. 9 illustrates a decoding example employing the sequential
22 decoder of FIG. 7. One bit is decoded for each two coded bits
23 entered into the shift register. The arrows from left to right
24 show the progression of the first pair of coded bits from the
input to the corresponding decoded data bit. The decoding
26 sequence is as follows: Initially, storage circuits 52, 54, 56,
27 and 58 are set to a word ending pattern (e.g., 0 0 0 1).
28 Coded data is entered into shift register 53 in synchronism with
29 clock 48. For the first four clock periods, the output of OR
circuit 78 is ignored. After three coded bits have been entered
SA973024 -9-
- ::
.
~ 1081~49
1 into shift register 53, the output of OR circuit 78 is used to
2 set decoded data bit values into latch 70, in synchronism with
3 clock 49, one decoded bit for each two coded bits entered. -
4 Following the entry of the last coded bit, three "dummy" bits
are entered to complete the decoding process.
6 Variations of the preferred embodiment with respect to
7 combinatorial encoding and decoding logic, number and arrangement
8 f auxiliary state variables and arrangement and timing of shift
registers are within the skill of the art.
The method described above can be used for encoding and/or
11 decoding with any fixed-rate code by use of shift registers of
12 suitable length, auxiliary state variables (where needed), and
13 appropriate configurations of combinatorial logic circuits.
14 Auxiliary state variables need not be used if the definition
1 5 of the code allows determination o the boundary between words by
16 examination of a fixed number of input bits (data bits for encoder
17 input; coded bits for decoder input), as for example in decoding
",~....
18 the (d,k) = (2,7) and (d,k) = (1,8) codes described in the related
19 patent 3,689,899
The number of shift register stages, the number of
21 auxiliary state variables, and the delay involved in encoding
22 or decoding are dependent upon the specification of code words
23 and the assignment of correspondences between data words and
24 code words.
26 WHAT IS CLAIMED IS:
27
28
29
.
SA973024 -10-
