el%3A19800160

plications and additions of this new scheme is substantially
fewer than is required by the conventional encoding
techniques.
An advantage of this new algorithm, aside from speed, is that
itsfirststep consists of performing a syndrome-like calculation,
which can be implemented by using the existing syndrome
algorithm used in the decoder. This fact can be used to lower
the total hardware cost of the encoder/decoder system.
Encoding procedure: Let n = 2m — 1 be the block length of a
R.S. code of designed distance d in GF(2m). The number of
m-bit message symbols is k = n — d + I.
To encode the k information symbols into an n = 2m - 1
symbol R.S. code word, one first defines the generator
polynomial
G(X)= ri (*-«*)
i=l
when a is a primitive nth root of unity. The code consists of all
multiples of G(x), subject to the constraint x" = 1.
Let at (for d — 1 <i <n — 1) be the message symbols, and
define
J(x) =
In order to generate the code word with information symbols
corresponding to I(x), proceed as follows: let
I(x)=Q(x)G(x)
(2)
where Q(x) is a quotient polynomial, G(x) is the generator
polynomial and R(x) is the remainder obtained by dividing
I(x) by G(x). Finally, I(x) is encoded into
C(x)=I(x)-R(x)
(3)
where a is an element of order 255 in GF(28), and a, = 0 for
0 < / < 31. Note that eqn. 5 is the same formula as eqn. 1 of
Reference 1. Thus, using the same procedure for computing
eqn. 1 as in Reference 1, one obtains /(a7) for 1 <j < 32. It
follows from Reference 1 that the total number of multiplications and additions needed to compute the /(a1) for
1 <j < 32 is 852 and 1804, respectively. The second step of the
encoding process is to compute R(x) defined in eqn. 4, i.e.
(6)
Since £,(x) can be precomputed, 32 x 30 = 960 multiplications and 960 additions are needed to compute R(x).
Hence the total number of multiplications and additions
required for encoding is 852 + 960=1812 and 1804 +
960 = 2764, respectively. In contrast, the total number of
multiplications and additions for encoding by conventional
methods is 223 x 32 = 7136 each.
Acknowledgment: The authors wish to thank Prof. J. Massey,
of the Electrical Engineering Department, University of California, Los Angeles for suggesting the possibility of a fast encoding algorithm of the type presented in this paper. This work
was supported by NASA contract NAS 7-100, and also in part
by the US Air Force Office of Scientific Research under grant
AFOSR 75-2798.
R. L. MILLER
7th January 1980
T. K. TRUONG
Communication Systems Research Section
Jet Propulsion Laboratory, Pasadena, California 91103, USA
I. S. REED
Department of Electrical Engineering
University of Southern California, Los Angeles, California 90007, USA
References
1
The new encoding procedure of an R.S. code is composed of
the following two steps:
(i) Compute 7(af) for 1 < / < d - 1 by the technique used to
compute syndromes in the decoder. Note that, by eqn. 3,
/(a1) = R(a') for 1 < i < d - 1.
TRUONG, T. K., MILLER, R. L., and REED, i. s.: 'Fast technique for
computing syndromes of B.C.H. and R.S. codes', Electron. Lett.,
1979, 15, pp. 720-721
2
PETERSON, w. w., and WELDON, E. J.: 'Error-correcting codes' (MIT
Press, 1972)
0013-5194/80/060222-02$U0/0
(ii) Compute R(x) from R(<xl) using Lagrange interpolation:
1= 1
where E,(x) is defined by
CONNECTION BETWEEN PRIMITIVE
GENERATORS OF GF(2n)
— iti
for 1 < ii < d - 1
(4)
Indexing terms: Codes, Polynomials, Sequences
Primitive polynomials over GF(2) are used for generating
The degree of £,(x) is d — 2, so the degree of R(x) is at most
maximal-length sequences. Powers of a root a of such a polyd — 2. Thus the parity symbols consist of the d — 1 coefficients
nomial are delay operators on the generated sequence. Given
two primitive polynomials of degree n with a, and <x2 their
of R{x), as desired. Note that a direct computation of R(x) in
roots, it is shown which parameter is needed in order to find
eqn. 2 involves (d — l)(n — d + ^multiplications and (d — 1) x
orj from a\ without knowledge of x.
(n — d+ 1) additions. If one uses a fast syndrome calculation,
say, for the case n = 255, k = 223, it is shown in the following
Introduction: A common method of generating binary seexample that the encoder requires only 1812 multiplications
quences is by linear feedback shift registers. If the feedback conand 2764 additions instead of 7136 multiplications and 7136
nections are made according to the coefficients of a primitive
additions, as required by a more conventional computation.
polynomial of degree n, the output sequence is of maximum
This results in a significantly faster encoding scheme.
periodicity, namely, the shift register passes through all 2" — 1
possible states (beside 'all 0') before it starts repeating itself.1
Example: Let n = 255 be the block length of an R.S. code of
8
The generated maximal-length sequence is usually called 'redesigned distance d = 33 over GF(2 ). This code will correct
sequence'. The following basic concepts are needed for further
any combination of 16 or fewer symbol errors. Thefirststep of
arguments.
the encoding process is to compute /(a1) for 1 < i < 32. That is,
Let /(x) be a primitive polynomial of degree n over GF(2)
let a be its root [a obeys the equation a" = aio"" 1 +
and
255-1
1
J
a
a"~
+ ... + an-ia. + 1, the coefficients a, being those of
2
I(a )=
for 1 <j < 32
(5)
/(x)]. Successive powers of a can be represented as polyELECTRONICS LETTERS
13th March 1980
Vol. 16 No. 6
223
nomials in a of degree n — 1, or as n-tuples consisting of the
coefficients of the polynomial representation. The n-tuples representing a1, 0 < i < 2" — 2, are all distinct, and with the 'all 0'
tuple they form the elements of GF(2"). The elements of GF(2")
can also be generated by the powers of the root of another
primitive polynomial of degree n. (There are 4>(2" — l)/n different primitive polynomials of degree n, where <f)(x) is the
number of positive integers smaller than x and relatively prime
to it.)
Powers of a act as delay operators on the m-sequence generated by/(x). Given an n-tuple in the sequence, the bit which
is x places further on is obtained by multiplying the n-tuple by
or* (scalar product of the given n-tuple, and the one representing <xx).
It should also be mentioned that calculating <xx from x (i.e.
finding its representation as a polynomial in a of degree n - 1),
involves 2n multiplications, at most. On the other hand,
finding x from a given <xx (e.g. finding a log in GF) is a very
complex operation. 2 ' 3
The delay properties of <xx, and the ease of calculating them
even for very large x, enable the finding of the pattern of any
n-tuple in a sequence, given its location (relative to a reference
n-tuple), without having to generate the sequence. Or equivalently, given an initial state of the sequence generator, it is
possible to calculate its state after x clockings, and this without
clocking it at all.
Given two n-tuples 7\ and T2 of a certain m-sequence, it is
possible to find (by solving a set of linear equations) <xx, where
x is the distance between 7\ and T2. Although it is practically
impossible to find x from <xx for very large 2", there might be a
positive answer to the following question. Given n-tuples 7\
and T2 in an m-sequence mu and given an n-tuple Kt in a
sequence m2 of the same length, is there such a parameter by
which an n-tuple V2 can be found in m2 such that the distance
between Vt and V2 is the same as that between 7\ and T21 Or
equivalently, given an m-sequence generator Gi and two of its
states Si and S2, is there a parameter which enables finding a
state in a generator G 2 , of the same length, whose distance (in
clock periods) from a given state Tx is the same as the distance
between Si and S 2 ?
This question is answered in detail in this letter by showing a
parameter which enables the finding of a* from a 2 , where ai
and <x2 are the roots of two primitive polynomials of the same
degree.
An obvious way of obtaining a* from bx for real a and b is by
raising bx to the yth power, where y — logj, a. Equivalently, in
order to find a* from a 2 , <x2 should be raised to the power
loga2 ai. However, loga2 a t has no meaning. The parameter
which connects a* and <x2 should therefore be found using a
completely different approach.
Theory: Let fx a n d / 2 be primitive polynomials of degree n.
Their primitive roots oti and <x2 each generate the elements of
GF(2n). The polynomials/ x a n d / 2 also generate m-sequences.
These sequences are denoted by mx and m 2 , respectively. There
exists a certain y where (2" — 1, y) = 1 such that if n^ is ydecimated (every yth element being taken) the elements of m2
are obtained successively.1 The sequence m t is obtained by
y~ ^decimating m 2 , where yy~l = 1 mod (2B — 1). For y being
a power of 2, y~l is also a power of 2 a n d / i = / 2 , where mi and
m2 are the same sequence shifted cyclically. The following
theorem refers to <xu a 2 and y mentioned above.
Theorem: Let P be an n x n matrix whose ith row, 0 < i <
n — 1, is aV- Then a 2 P = axy for any x.
Proof:
Notation:
(a) A sequence is decimated starting with a vector A iff A is a
substring of the sequence, and it is decimated starting with the
first element of A.
(b) Vectors are x placed apart in a sequence iff their first ele
ments are x places apart.
Let A and B be n-tuples such that when mx is y-decimated
224
starting with A, the sequence m2 is obtained starting with B.
Without loss of generality we can assume that mi and m2 start
with A and B, respectively (otherwise, we shift them cyclically
until the requirement is fulfilled). Let M and N be n x n
matrices whose ith row, 0 < i < n — 1, is the n-tuple starting
with the ith place in mi and m2, respectively. Let D be an
n-tuple in mx starting with the x place. If mx is y-decimated
starting with D, the sequence m2 is obtained starting with a
vector E which is xy" 1 places from B.
The following facts can easily be verified:
(a) M and N are symmetric
(b) D = z\M
(c) E = ax2'yN
(d) DP' = E, E(P')~l = D where the ith row of P~l is aliy
[(a) follows from the definition of M and N. The rest follow
from the delay operation of a*. The form of P " x follows from
the fact that mi is recovered by y~ ^decimating m 2 , where the
ith row of P is aV]
It follows that ux2hN(P')~*M~l = a i ' f n order to prove the
theorem it has to be proved that NiP')'1 = PM.
The ij element of N(Pt)~l is the (i + jy~ J )th element of m 2 .
The ij element of PM is the (iy +;)th element of mx. Since
every element in the /cth place in m2 appears in mi in the (fey)th
place, and since (i +jy~l)y — iy +j, it follows that
N(P')~l = PM and the theorem is thus proved. (The feth element of mi and m2 is defined with respect to A and B).
The theorem shows that the parameter which enables the
finding of a* from a 2 is y. (The matrix P is constructed from y,
resulting in a.X3>. Raising this result to the power y'1, which is
known if y is known, results in a*.) It is not claimed that y can
be recovered from/i and/ 2 . What is shown is that one parameter enables the finding of a* from a% for any x.
Illustration: Let
fx = xs + x2 + l , / 2 = x 5 + x 4 + x 3 + x 2 + 1
m, = 1 0 0 0 0 I 0 0 1 0 1 1 0 U 1 1 1 I I 0 0 0 1 I 0 1 1 1 0 1 0
m2
= 1 0 0 0 0 1 1 0 0 1 0 0 1 1 1 1 1 0 1 1 1 0 0 0 1 0 1 0 1 1 0
If every third element is taken from mi, the sequence m2 is
obtained. mx is obtained from m2 by taking every 21st element
of the latter ( 3 x 2 1 = 1 mod 31). We thus have y = 3 and
P=
10 0 0 0
0 0 0 10
0 10 10
0 10 11
0 1 1 1 0
Now take, for example, a | = 0 0
1 1 1
Conclusion: It has been shown how to execute an operation
which is equivalent to the abstract idea of raising a 2 to the
power loga2 ot|, where a t and a 2 are primitive elements of
GF(2"). The operation was performed using one constant
parameter. A question which was not answered is the following
one. Given any integer x, is it possible to find a y such that
orl = a 2 , using a constant parameter? (An operation which is
equivalent of the abstract idea of multiplying x by loga2 a t .)
Any suggestion by readers will be highly appreciated.
BENJAMIN ARAZI
23rd January 1980
Department of Electrical Engineering
Ben-Gurion University of the Negev
PO Box 653, Beer-Sheva 84120, Israel
References
1 GOLOMB, s. w.: 'Shift register sequences' (Holden-Day, San Francisco, 1967)
ELECTRONICS LETTERS
13th March 1980
Vol. 16
No. 6
2 POHLIG, s. c , and HELLMAN, M. E.: 'An improved algorithm for
computing logarithms over GF(p) and its cryptographic
significance', IEEE Trans., 1978, IT-24, pp. 106-110
3 ADLEMAN, L.: 'A subexponential algorithm for the discrete logarithm problem with applications to cryptography', (working
abstract)
0013-5194/80/060223-03$! 50/0
CIRCUIT IMPLEMENTATION OF CURRENT
CONVEYOR
definition, but we shall use it because it can be useful in many
applications (see Reference 6, for example, or consider the
implementation of a current-summing amplifier).
Basic circuit: Application of a synthesis technique described by
the author and a co-worker8 leads to an efficient implementation of expr. 1. From the hybrid description of the c.c,
we obtain the circuit of Fig. 1. It is simple to check that the
network description corresponds with eqn. 1 if the summers
are ideal, in the sense that the input current flows entirely
through R. It is not a severe constraint, as was shown in Reference 8, and can be reasonably performed by selecting adequate
resistor ratios.
Simplified circuit: The general circuit described above can be
simplified when one intends to design either a c.c.I or a cell.
That expression can be rearranged as follows:
'y
Indexing terms: Circuit design, Networks, Integrated circuits
Some circuits for the design of current conveyors are
reported. The new configurations use a minimum number of
operational amplifiers. Experimental data on their performance is compared with other realisations.
Introduction: Current conveyors12 have been widely used as a
basic building block for active-circuit synthesis. Many applications have been reported elsewhere.1"4 However, little effort
has been devoted to practical design techniques for the different types of current conveyors.5"7 Very recently, Senani7
proposed a circuit configuration which can be considered as
the more efficient implementation we know. Nevertheless, the
new circuit has the drawback of requiring two active elements
of different nature. It uses an operational amplifier (o.a.) and
an operational transconductance amplifier (o.t.a.) as well as
two resistors. I agree with the author that the new
configuration is theoretically suitable for integration on one
chip. However, actual implementation requires one to employ
two different chips, since o.a.s and o.t.a.s are not commercially
available on the same i.e.
The purpose of this letter is to report new structures for
current conveyors based entirely on o.a.s. Several reasons can
be given for doing this, besides the elegance of a design
technique based on only one class of active elements.
Current-conveyor characterisation: General current conveyors
can be defined as grounded 3-port network elements described
by
h
iz
v_
=
0 0 ii a
0_ 0
\
c 0 ;o~
b
=
' 0 1,0"
a 0 !o
. ± 1 O'O.
Vy
(2)
Jz .
.Vz.
It suggests that, for a = 1, the summers enclosed into a dashed
line rectangle in Fig. 1 can be substituted by a simpler implementation of a c.n.i.c The direct replacement is shown in Fig.
2, which is in fact an o.a. version of Senani's circuit. Routine
analysis gives eqn. 2 when we make i?t = R2 and R3 = /? 4 . The
sign + or — can be obtained by interchanging the terminals of
A2. Also, a c e l l may be realised by eliminating the resistor
connected between the + terminal and the output of At.
However, the new circuit exhibits (like Senani's circuit)
unsymmetrical behaviour due to the fact that equivalent resistors at ports X and Y are not equal; this influences the
relation iy = ix. A more balanced realisation is shown in Fig. 2,
when we connect resistor R'2 and make R2 = R2 = 2Rt.
|879/2|
Fig. 2 Simplified circuit for current conveyors
Vy
vz
(1)
where, usually, b = ± 1, c = 1 and a = 1 for a first-generation
current conveyor (c.c.I) and a = 0 for a second-generation current conveyor (cell). Expr. 1 is more general than the normal
Experimental results: The circuit described above has been
breadboarded by using \iklW (dual o.a.) and standard resistors. Values of 1 kQ for R and 100 kQ for the other resistors
(except for R2 and R'2 of Fig. 2 which were 200 kQ resistors)
have been chosen. Port Y was driven by a voltage source and
loaded ports X and Z with resistors of 5-6 kQ. In this condition,
a sinusoidal input signal of 10 V peak-peak produces no
appreciable distortion up to 16 kHz. Only a small phase shift
was observed at port Z. Empirical data for Senani's circuit
have been collected for comparison. We have used the same
o.a.s and a CA3080 o.t.a. With the 5-6 kQ loads, the response
was very poor, due to the low signal-handling capabilities of
the o.t.a. For 56 kQ loads, we have obtained a similar performance for the new circuits and Senani's circuit. However, for
the latter, the offset must be adjusted and additional circuitry
has to be employed tofixethe o.t.a. transconductance value.
Discussion: The circuit of Fig. 2 compares favourably with
older c.c realisations.56 Comparison with Reference 7 has to
be carried out with care. In that sense, we quote:
(a) The new circuits exclusively used o&s. Only one integrated
chip is needed.
1879/11
Fig. 1 Realisation scheme of a general current conveyor
ELECTRONICS LETTERS
(b) Experimental data reveals superiority of the new circuits for
medium and high currents due to the low maximum output
13th March 1980 Vol. 16 No. 6
225