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
1/--страниц