High-radix transforms for Reed-Solomon codes over Fermat primes (Corresp.)

It is shown that a high-radix fast Fourier transform (FFT) with generatorgamma = 3over GF(F_{n}), whereF_{n} = 2^{2}^{n'} + 1is a Fermat prime, can be used for encoding and decoding of Reed-Solomon (RS) codes of length2^{2}^{n}. Such an RS decoder is considerably faster than a decoder using the usual radix 2 FFT. This technique applies most ideally to a 16-error-correcting, 256-symbol RS code of 8 bits being considered currently for space communication applications. This special code can be encoded and decoded rapidly using a high-radix FFT algorithm over GF(F_{3}).     

Sequences achieving the boundary of the entropy region for a two-source are virtually memoryless (Corresp.)

For a joint distribution{rm dist}(X,Y), the functionT(t)=min { H(Y|U): I(U wedge Y|X)=O, H(X|U)geq t}is an important characteristic. It equals the asymptotic minimum of(1/n)H(Y^{n})for random pairs of sequences(X^{n}, Y^{n}), wherefrac{1}{n} sum ^{n}_{i=1}{rm dist} X_{i} sim {rm dist} X, {rm dist} Y^{n}|X^{n} = ({rm dist} Y|X)^{n}, frac{1}{n}H(X^{n})geq t.We show that if, for(X^{n}, Y^{n})as given, the rate pair[(1/n)H(X^{n}),(1/n)H(Y^{n})]approaches the nonlinear part of the curve(t,T(t)), then the sequenceX^{n}is virtually memoryless. Using this, we determine some extremal sections of the rate region of entropy characterization problems and find a nontrivial invariant for weak asymptotic isomorphy of discrete memoryless correlated sources.     

Normal basis of finite fieldGF(2^m)(Corresp.)

Massey and Omura recently developed a new multiplication algorithm for Galois fields based on the normal basis representation. This algorithm shows a much simpler way to perform multiplication in finite field than the conventional method. The necessary and sufficient conditions are presented for an element to generate a normal basis in the field GF(2^{m}), wherem = 2^{k}p^{n}andp^{n}has two as a primitive root. This result provides a way to find a normal basis in the field.     

Hypothesis testing with multiterminal data compression

The multiterminal hypothesis testingH: XYagainstH̄: X̄Ȳis considered whereX^{n} (X̄^{n})andY^{n} (Ȳ^{n})are separately encoded at ratesR_{1}andR_{2}, respectively. The problem is to determine the minimumbeta_{n}of the second kind of error probability, under the condition that the first kind of error probabilityalpha_{n} leq epsilonfor a prescribed0 < epsilon < 1. A good lower boundtheta_{L}(R_{1}, R_{2})on the power exponenttheta (R_{1}, R_{2},epsilon)= lim inf_{n rightarrow infty}(-1/n log beta_{n})is given and several interesting properties are revealed. The lower bound is tighter than that of Ahlswede and Csiszár. Furthermore, in the special case of testing against independence, this bound turns out to coincide with that given by them. The main arguments are devoted to the special case withR_{2} = inftycorresponding to full side information forY^{n}(Ȳ^{n}). In particular, the compact solution is established to the complete data compression cases, which are useful in statistics from the practical point of view.     

On the weight distribution of binary linear codes (Corresp.)

LetVbe a binary linear(n,k)-code defined by a check matrixHwith columnsh_{1}, cdots ,h_{n}, and leth(x) = 1ifx in {h_{1}, cdots , h_{n}, andh(x) = 0ifx in neq {h_{1}, cdots ,h_{n}}. A combinatorial argument relates the Walsh transform ofh(x)with the weight distributionA(i)of the codeVfor smalli(i< 7). This leads to another proof of the Plessith power moment identities fori < 7. This relation also provides a simple method for computing the weight distributionA(i)for smalli. The implementation of this method requires at most(n-k+ 1)2^{n-k}additions and subtractions,5.2^{n-k}multiplications, and2^{n-k}memory cells. The method may be very effective if there is an analytic expression for the characteristic Boolean functionh(x). This situation will be illustrated by several examples.     

A dichotomy of functionsF(X, Y)of correlated sources(X, Y)

Consider separate encoding of correlated sourcesX^{n}=(X_{l}, cdots ,X_{n}), Y^{n} = (Y_{l}, cdots ,Y_{n})for the decoder to reliably reproduce a function{F(X_{i}, Y_{i})}^{n}_{i=1}. We establish the necessary and sufficient condition for the set of all achievable rates to coincide with the Slepian-Wolf region whenever the probability densityp(x,y)is positive for all(x,y).     

On certain projective geometry codes (Corresp.)

LetVbe an(n, k, d)binary projective geometry code withn = (q^{m}-1)/(q - 1), q = 2^{s}, andd geq [(q^{m-r}-1)/(q - 1)] + 1. This code isr-step majority-logic decodable. With reference to the GF(q^{m}) = {0, 1, alpha , alpha^{2} , cdots , alpha^{n(q-1)-1} }, the generator polynomialg(X), ofV, hasalpha^{nu}as a root if and only ifnuhas the formnu = i(q - 1)andmax_{0 leq l < s} W_{q}(2^{l} nu) leq (m - r - 1)(q - 1), whereW_{q}(x)indicates the weight of the radix-qrepresentation of the numberx. LetSbe the set of nonzero numbersnu, such thatalpha^{nu}is a root ofg(X). LetC_{1}, C_{2}, cdots, C_{nu}be the cyclotomic cosets such thatSis the union of these cosets. It is clear that the process of findingg(X)becomes simpler if we can find a representative from eachC_{i}, since we can then refer to a table, of irreducible factors, as given by, say, Peterson and Weldon. In this correspondence it was determined that the coset representatives for the cases ofm-r = 2, withs = 2, 3, andm-r=3, withs=2.     

Electromagnetic reflection from an extended turbulent medium: Cumulative forward-scatter single-backscatter approximation

The backscatter cross sectionQfor high-frequency irradiated turbulent dielectric media, many mean free pathsL_{1}wide, is computed. The lengthL_{1}is the distance into the medium over which the mean electric field decreases in amplitude by a factore^{-1}. Previous calculations have always been restricted toL ll L_{1}. It is found thatQincreases from the Born approximationQ = Q_{1}for medium widthL ll L_{1}toQ = 2Q_{1}forL gg L_{1}, and the theory is valid as long asL ll (kL_{0})^{5/3} L_{1}, a significant improvement over the Born approximation, when the macroscaleL_{0}is much larger than the wavelength2_{pi}k^{-1}. The improvement is due to incorporation of the dominant effects of cumulative forward scattering in the local electric field in the medium. A rigorous and a heuristic derivation are given. The transitional behavior is discussed and a simple physical interpretation is given.     

On the distribution of de Bruijn sequences of given complexity

The distributiongamma (c, n)of de Bruijn sequences of ordernand linear complexitycis investigated. It is shown that forn geq 4, gamma (2^{n} - 1, n) equiv 0 pmod{8}, and fork geq 3, gamma (2^{2k} - 1,2k) equiv 0 pmod{l6}. It is also shown thatgamma (c, n) equiv 0 pmod{4}for allc, andn geq 3such thatcnis even.     

The fast decoding of Reed-Solomon codes using Fermat transforms (Corresp.)

It is shown thatsqrt[8]{2}is an element of order2^{n+4}inGF(F_{n}), whereF_{n}=2^{2^{n}}+1is a Fermat prime forn=3,4. Hence it can be used to define a fast Fourier transform (FFT) of as many as2^{n+4}symbols inGF(F_{n}). Sincesqrt[8]{2}is a root of unity of order2^{n+4}inGF(F_{n}), this transform requires fewer muitiplications than the conventional FFT algorithm. Moreover, as Justesen points out [1], such an FFT can be used to decode certain Reed-Solomon codes. An example of such a transform decoder for the casen=2, wheresqrt{2}is inGF(F_{2})=GF(17), is given.     

A method for computing addition tables inGF(p^n)(Corresp.)

Conway showed that a table of Zech's logarithms is useful to perform addition in GF(p^{n})when the elements are represented as powers of a primitive element. The Zech's logarithmZ(x)ofxis defined by the equationalpha^{z(x)}=alpha^{x} + 1, wherealphais a primitive element, zero is written asalpha^{ast}, andx=ast,O,1, cdots ,p^{n}-2. A simple algorithm for making a table of Zech's logarithms is presented.     

Successive encoding of correlated sources

The encoding of a discrete memoryless multiple source{( X_{i}, Y_{i})}_{i=1}^{infty}for reconstruction of a sequence{Z_{i}}_{i=1}^{infty}}, withZ_{i} = F( X_{i}, Y_{i}); i = 1,2, cdotsis considered. We require that the encoding should be such that{X_{i}}_{i=1}^{infty}is encoded first without any consideration of{Y_{i}}_{i=1}^{infty}, while in a second part of the encoding, this latter sequence is encoded based on knowledge of the outcome of the first encoding. The resulting scheme is called successive encoding. We find general outer and inner bounds for the corresponding set of achievable rates along with a complete single letter characterization for the special caseH( X_{i}|Z_{i}, Y_{i}) = 0. Comparisons with the Slepian-Wolf problem and the Ahlswede-Korner-Wyner side information problem are carried out.     

Estimation of the mean with time-varying finite memory (Corresp.)

LetX_1,X_2,cdotsbe a sequence of independent identically distributed observations with a common meanmu. Assume that0 leq X_i leq 1with probability 1. We show that for eachvarepsilon > 0there exists an integerm, a finite-valued statisticT_n = T_n(X_1, cdots , X_n) in {t_1,cdots,t_m}and a real-valued functionddefined on{t_1,cdots,t_m}such thati)T_{n+1} = f_n(T_n,X_{n+1}); ii)P[lim sup mid d(T_n) - mu mid leq varepsilon] = 1. Thus we have a recursive-like estimate ofmu, for which the data are summarized for eachnby one ofmstates and which converges to withinvarepsilonofmuwith probability 1. The constraint on memory here is time varying as contrasted to the time-invariant constraint that would haveT_{n+1} = f(T_n, X_{n+1})for alln.     

On the survival of sequence information in filters (Corresp.)

Given a binary data streamA = {a_i}_{i=o}^inftyand a filterFwhose output at timenisf_n = sum_{i=0}^{n} a_i beta^{n-i}for some complexbeta neq 0, there are at most2^{n +1)distinct values off_n. These values are the sums of the subsets of{1,beta,beta^2,cdots,beta^n}. It is shown that all2^{n+1}sums are distinct unlessbetais a unit in the ring of algebraic integers that satisfies a polynomial equation with coefficients restricted to +1, -1, and 0. Thus the size of the state space{f_n}is2^{n+1}ifbetais transcendental, ifbeta neq pm 1is rational, and ifbetais irrational algebraic but not a unit of the type mentioned. For the exceptional values ofbeta, it appears that the size of the state space{f_n}grows only as a polynomial innifmidbetamid = 1, but as an exponentialalpha^nwith1 < alpha < 2ifmidbetamid neq 1.     

Photosolubility of diazoquinone resists

The photochemical properties of a diazoquinone/novolak resist system were studied over a wide range of material and processing parameters in order to determine the optimum values for a given application. These resists are representative of the commercial positive-working photoresists being used for high-resolution lithography. The solubility of the resist in an alkaline developer depends on exposure E asDelta g^{-1} = [g_{0}(E/E_{e})^{m}]^{-1} + [Delta g_{infin}]^{-1}where the net development rate (Delta g) is the difference between solubility rates of the exposed (g) and unexposed (g0) sample. Three of these parameters characterize the lithographic response of the resist. They depend mainly on the resist composition but not on the processing conditions. Eeis a measure of the sensitivity and ranges from 10 to 20 mJ/cm²of 405-nm light for useful resist formulations. The contrast parameter (m) increases slowly with sensitizer concentration while the saturated solubility ratio (g_{infin}/g_{0}) inereases very rapidly. The fourth parameter (g0) depends strongly on processing parameters. It can readily be set to provide the desired development time, e.g., by adjusting the developer strength. On a more fundamental level, it is found that the dependence of the solubility on exposure can be expressed in a unified manner for all the resist formulations studied asg approx g_{0} exp (2 times 10^{-20} n_{e})where neis the number of exposed sensitizer molecules per cubic centimeter.     

Higher dimensional orthogonal designs and applications

The concept of orthogonal design is extended to higher dimensions. A properg-dimensional design[d_{ijk cdots upsilon}]is defined as one in which all parallel(g-1)-dimensional layers, in any orientation parallel to a hyper plane, are uncorrelated. This is equivalent to the requirement thatd_{ijk cdots upsilon} in {0, pm x_{1}, cdots , pm x_{t} }, wherex_{1}, cdots , x_{t}are commuting variables, and thatsum_{p} sum_{q} sum_{r} cdots sum_{y} d_{pqr cdots ya} d_{pqr cdots yb} = left( sum_{t} s_{i}x_{i}^{2} right)^{g-1} delta ab,where(s{1}, cdots , s{t})are integers giving the occurrences ofpm x_{1}, cdots , pm x_{t}in each row and column (this is called the type(s_{1}, cdot ,s_{t})^{g-1})and(pqr cdots yz)represents all permutations of(ijk cdots upsilon). This extends an idea of Paul J. Shlichta, whose higher dimensional Hadamard matrices are special cases withx_{1}, cdots , x_{t} in {1,- 1}, (s_{1}, cdots, s_{t})=(g), and(sum_{t}s_{i}x_{i}^{2})=g. Another special case is higher dimensional weighing matrices of type(k)^{g}, which havex_{1}, cdots , x_{t} in {0,1,- 1}, (s_{1}, cdots, s_{t})=(k), and(sum_{t}s_{i}x_{i}^{2})=k. Shlichta found properg-dimensional Hadamard matrices of size(2^{t})^{g}. Proper orthogonal designs of type     

Two-dimensional dynamic analysis of short-channel thin-film MOS transistors using a minicomputer

A computer program is described for simulating two-dimensional thin-film MOS transistors on a minicomputer. Data are presented showing the variation of internal carrier density with time until a steady-state condition is reached. These data show the formation of a drain-induced back channel whose conduction properties depend on the back-channel length and carrier mobility. For channel length below 2.0 µm, the two-dimensional steady-state drain current is shown to fit the expressionI_{D}/W = frac{micro_{0}C_{0}}{L[1+(micro_{0}/upsilon_{s} V_{D}{L})^{2}]^{1/2}}(V_{G} - V_{T} - V_{D/2})V{D}for values of drain voltage below a specific saturation value (V_{DM}); andI_{D}/W = frac{10^{-8)(V_{G} - V_{T})^{1/2}}{(T_{ox})^{1/2}L}.(V_{D} - V_{DM}) + I_{DM}for drain voltages above the saturation value.     

Characterization theorems for extending Goppa codes to cyclic codes (Corresp.)

Several theorems are presented which characterize Goppa codes having the property of becoming cyclic when an overall parity cheek is added. If such a Goppa code has location setL = GF (q^{m})and a Goppa polynomialg(z)that is irreducible overGF(q^{m}), theng(z)must be a quadratic. Goppa codes defined by(z- beta)^{a}and location setLwith cardinalitynsuch thatn+l|q^{m}-1are considered along with their subcodes. A sufficient condition onLis derived for the extended codes to become cyclic. This condition is also necessary whena= 1. The construction ofLfor differentnsatisfying the stated condition is investigated in some detail. Some irreversible Goppa codes have been shown to become cyclic when extended by an overall parity check.