共查询到20条相似文献,搜索用时 31 毫秒
1.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1986,32(2):284-285
It is shown that a cyclic codeC of lengthq over GF(q) is the maximum distance separable if and only if either1) q is a prime, in which caseC is equivalent, up to a coordinate permutation, to an extended Reed-Solomon code, or2) C is a trivial code of dimensionk in {1, q - 1, q } . Hence there exists a nontrivial cyclic extended Reed-Solomon code of lengthq over GF(q) if and only ifq is a prime. 相似文献
2.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1986,32(3):436-440
Using earlier methods a combinatorial upper bound is derived for|C|. cdot |D| , where(C,D) is adelta -decodable code pair for the noisy two-access binary adder channel. Asymptotically, this bound reduces toR_{1}=R_{2} leq frac{3}{2} + elog_{2} e - (frac{1}{2} + e) log_{2} (1 + 2e) = frac{1}{2} - e + H(frac{1}{2} - e) - frac{1}{2}H(2e), wheree = lfloor (delta - 1)/2 rfloor /n, n rightarrow infty andR_{1} resp.R_{2} is the rate of the codeC resp.D . 相似文献
3.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1975,21(2):228-230
LetP(i)= (1 - theta)theta^i be a probability assignment on the set of nonnegative integers wheretheta is an arbitrary real number,0 < theta < 1 . We show that an optimal binary source code for this probability assignment is constructed as follows. Letl be the integer satisfyingtheta^l + theta^{l+1} leq 1 < theta^l + theta^{l-1} and represent each nonnegative integeri asi = lj + r whenj = lfloor i/l rfloor , the integer part ofi/l , andr = [i] mod l . Encodej by a unary code (i.e.,j zeros followed by a single one), and encoder by a Huffman code, using codewords of lengthlfloor log_2 l rfloor , forr < 2^{lfloor log l+1 rfloor} - l , and lengthlfloor log_2 l rfloor + 1 otherwise. An optimal code for the nonnegative integers is the concatenation of those two codes. 相似文献
4.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1984,30(2):385-388
LetV be 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 ifnu has 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-q representation of the numberx . LetS be 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 thatS is 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 . 相似文献
5.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1985,31(6):826-830
It is shown that the family ofq -ary generalized Reed-Solomon codes is identical to the family ofq -ary linear codes generated by matrices of the form[I|A] , whereI is the identity matrix, andA is a generalized Cauchy matrix. Using Cauchy matrices, a construction is shown of maximal triangular arrays over GF(q) , which are constant along diagonals in a Hankel matrix fashion, and with the property that every square subarray is a nonsingular matrix. By taking rectangular subarrays of the described triangles, it is possible to construct generator matrices[I|A] of maximum distance separable codes, whereA is a Hankel matrix. The parameters of the codes are(n,k,d) , for1 leq n leq q+ 1, 1 leq k leq n , andd=n-k+1 . 相似文献
6.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1983,29(1):136-137
Given a positive integerk and a prime powerq withq leq k , it is proved that the largest value ofn for which there exists an[n,k,n-k+l] maximum distance separable (MDS) code over GF(q) isk+1 . A simple proof for the largest value ofn for which there exists an[n,2,n-1] MDS code over any finite field is also given. 相似文献
7.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1984,30(3):480-484
Two algorithms are presented for the generation of full-length shift-register cycles, also referred to as de Bruijn sequences. The first algorithm generates2^{k cdot g(n,k) full cycles of length2^{n} , using3n + k cdot g(n, k) bits of storage, wherek is a free parameter in the range1 leq k leq 2^{((n-4)/2)} , andg(n, k) is of the order ofn - 2 log k . The second algorithm generates about2^{n^{2}/4} full cycles of length2^{n} , using aboutn^{2}/2 bits of storage. In both algorithms, the time required to produce the next bit from the lastn bits is close ton . A possible application to the construction of stream ciphers is indicated. 相似文献
8.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1972,18(2):310-312
Given a binary data streamA = {a_i}_{i=o}^infty and a filterF whose output at timen isf_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 unlessbeta is 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} ifbeta is transcendental, ifbeta neq pm 1 is rational, and ifbeta is 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 inn ifmidbetamid = 1 , but as an exponentialalpha^n with1 < alpha < 2 ifmidbetamid neq 1 . 相似文献
9.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1984,30(5):769-771
A general product construction for perfect single-error-correcting codes over an arbitrary alphabet is presented. Given perfect single-error-correcting codes of lengthsn, m , andq + 1 over an alphabet of orderq , one can construct perfect single-error-correcting codes of length(q - 1)nm + n + m over the same alphabet. Moreover, if there exists a perfect single-error-correcting code of lengthq + 1 over an alphabet of orderq , then there exist perfect single-error-correcting codes of lengthn ,n = (q^{t} _ 1)/(q - 1) , and(t > 0 , an integer). Finally, connections between projective planes of orderq and perfect codes of lengthq + 1 over an alphabet of orderq are discussed. 相似文献
10.
In this paper we investigate the performance of maximum-distance-separable codes with symbols fromGF(q) when they are used for pure error detection or for simultaneous error correction and detection over aq -input andq -output discret memoryless channel with symbol error probability ε. First we show that the probability of undetected error for an MDS code used for pure error detection is upper bounded byq^{-r} and decreases monotonically as εdecreases from(q - 1)/q to 0, wherer is the number of parity-check symbols of the code. Then we show that the probability of undetected error for an MDS code used for correctingt or fewer symbol errors is upper bounded byq^{-r} Summin{i=0}max{t}(min{i} max{n})(q - 1)^{i} and decreases monotonically as ε decreases from(q - 1)/q to 0. These results show that the MDS codes are effective for both pure error detection and simultaneous error correction and detection. 相似文献
11.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1978,24(4):497-499
It is shown thatsqrt[8]{2} is an element of order2^{n+4} inGF(F_{n}) , whereF_{n}=2^{2^{n}}+1 is 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. 相似文献
12.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1984,30(6):872-877
Winograd's result concerning Elias' model of computation in the presence of noise can be stated without reference to computation. If a codevarphi: {0,1}^{k} rightarrow {0,1}^{n} is min-preserving(varphi (a wedge b) = varphi (a) wedge varphi (b) fora,b in {0,1}^{k}) andepsilon n -error correcting, then the ratek/n rightarrow 0 ask rightarrow infty . This result is improved and extended in two directions. begin{enumerate} item For min-preserving codes with {em fixed} maximal (and also average) error probability on a binary symmetric channel againk/n rightarrow 0 ask rightarrow infty (strong converses). item Second, codes with lattice properties without reference to computing are studied for their own sake. Already for monotone codes( varphi (a) leq varphi (b) fora leq b) the results in direction 1) hold for maximal errors. end{enumerate} These results provide examples of coding theorems in which entropy plays no role, and they can be reconsidered from the viewpoint of multiuser information theory. 相似文献
13.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1965,11(1):107-112
A method is shown by which it is possible to establish the existence (or nonexistence) of the comma-free properties of any group code from a simple observation of its null-space. Using this technique it is then demonstrated that all(n, k) {em cyclic} group error-correcting code dictionaries can be made comma-free (without adding further redundancy or altering their error-correcting properties) if, and only if,k leq (n - 1)/2 . Ifk is larger than(n - 1)/2 it is still possible to detect bit gains or losses of up ton-k-1 code bits. 相似文献
14.
Writing on dirty paper (Corresp.) 总被引:1,自引:0,他引:1
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1983,29(3):439-441
A channel with outputY = X + S + Z is examined, The stateS sim N(0, QI) and the noiseZ sim N(0, NI) are multivariate Gaussian random variables (I is the identity matrix.). The inputX in R^{n} satisfies the power constraint(l/n) sum_{i=1}^{n}X_{i}^{2} leq P . IfS is unknown to both transmitter and receiver then the capacity isfrac{1}{2} ln (1 + P/( N + Q)) nats per channel use. However, if the stateS is known to the encoder, the capacity is shown to beC^{ast} =frac{1}{2} ln (1 + P/N) , independent ofQ . This is also the capacity of a standard Gaussian channel with signal-to-noise power ratioP/N . Therefore, the stateS does not affect the capacity of the channel, even thoughS is unknown to the receiver. It is shown that the optimal transmitter adapts its signal to the stateS rather than attempting to cancel it. 相似文献
15.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1981,27(6):807-808
The binary image of an extended Reed-Solomon code overF_{16} relative to a trace-orthogonal basis ofF_{l6} is an extremal doubly even self-dual code(64,32,12) . 相似文献
16.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1976,22(3):363-366
This article presents new tighter upper bounds on the rate of Gaussian autoregressive channels with linear feedback. The separation between the upper and lower bounds is small. We havefrac{1}{2} ln left( 1 + rho left( 1+ sum_{k=1}^{m} alpha_{k} x^{- k} right)^{2} right) leq C_{L} leq frac{1}{2} ln left( 1+ rho left( 1+ sum_{k = 1}^{m} alpha_{k} / sqrt{1 + rho} right)^{2} right), mbox{all rho} , whererho = P/N_{0}W, alpha_{l}, cdots, alpha_{m} are regression coefficients,P is power,W is bandwidth,N_{0} is the one-sided innovation spectrum, andx is a root of the polynomial(X^{2} - 1)x^{2m} - rho left( x^{m} + sum^{m}_{k=1} alpha_{k} x^{m - k} right)^{2} = 0. It is conjectured that the lower bound is the feedback capacity. 相似文献
17.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1977,23(6):776-778
It is shown that a high-radix fast Fourier transform (FFT) with generatorgamma = 3 over GF(F_{n}) , whereF_{n} = 2^{2}^{n'} + 1 is 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}) . 相似文献
18.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1984,30(6):868-870
A linear codeC over GF(q) is good fort -error-correction and error detection ifP(C,t;epsilon) leq P(C,t;(q - 1)/q) for allepsilon, 0 leq epsilon leq (q - 1)/q , whereP(C, t; epsilon) is the probability of an undetected error after a codeword inC is transmitted over aq -ary symmetric channel with error probabilityepsilon and correction is performed for all error patterns witht or fewer errors. A sufficient condition for a code to be good is derived. This sufficient condition is easy to check, and examples to illustrate the method are given. 相似文献
19.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1966,12(2):148-153
Given a graphG ofn nodes. We wish to assign to each nodei(i = 1, 2, cdots n) a unique binary codec_{i} of lengthm such that, if we denote the Hannuing distance betweenc_{i} andc_{j} asH(c_{i}, c_{j}) , thenH(c_{i}, c_{j})leq T if nodesi andj are adjacent (i.e., connected by a single branch), andH(c_{i}, c_{j}) geq T+1 otherwise. If such a code exists, then we say thatG is doable for the value ofT and tn associated with this code. In this paper we prove various properties relevent to these codes. In particular we prove 1) that for every graphG there exists anm andT such thatG is doable, 2) for every value ofT there exists a graphG̃ which is notT doable, 3) ifG isT' doable, then it isT'+ 2p doable forp = 0, 1, 2, cdots , and is doable for allT geq 2T' ifT' is odd, and is doable for allT geq 2T' + 1 ifT' is even. In theory, the code can be synthesized by employing integer linear programming where eitherT and/orm can be minimized; however, this procedure is computationally infeasible for values ofn andm in the range of about10 or greater. 相似文献
20.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1987,33(6):919-923
LetC be the cyclic product code ofp single parity check codes of relatively prime lengthsn_{1}, n_{2},cdots , n_{p} (n_{1} < n_{2} < cdots < n_{p}) . It is proven thatC can correct2^{P-2}+2^{p-3}-1 bursts of lengthn_{1} , andlfloor(max{p+1, min{2^{p-s}+s-1,2^{p-s}+2^{p-s-1}}}-1)/2rfloor bursts of lengthn_{1}n_{2} cdots n_{s} (2leq s leq p-2) . Forp=3 this means thatC is double-burst-n_{1} -correcting. An efficient decoding algorithm is presented for this code. 相似文献