共查询到20条相似文献,搜索用时 15 毫秒
1.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1984,30(2):395-403
For any(n, k, d) binary linear code, the Griesmer bound says thatn geq sum_{i=0}^{k-1} lceil d/2^{i} rceil , wherelceil x rceil denotes the smallest integergeq x . We consider codes meeting the Griesmer bound with equality. These codes have parametersleft( s(2^{k} - 1) - sum_{i=1}^{p} (2^{u_{i}} - 1), k, s2^{k-1} - sum_{i=1}^{p} 2^{u_{i} -1} right) , wherek > u_{1} > cdots > u_{p} geq 1 . We characterize all such codes whenp = 2 oru_{i-1}-u_{i} geq 2 for2 leq i leq p . 相似文献
2.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1986,32(5):706-709
Recently Kasami {em et al.} presented a linear programming approach to the weight distribution of binary linear codes [2]. Their approach to compute upper and lower bounds on the weight distribution of binary primitive BCH codes of length2^{m} - 1 withm geq 8 and designed distance2t + 1 with4 leq t leq 5 is improved. From these results, the relative deviation of the number of codewords of weightjleq 2^{m-1} from the binomial distribution2^{-mt} left( stackrel{2^{m}-1}{j} right) is shown to be less than 1 percent for the following cases: (1)t = 4, j geq 2t + 1 andm geq 16 ; (2)t = 4, j geq 2t + 3 and10 leq m leq 15 ; (3)t=4, j geq 2t+5 and8 leq m leq 9 ; (4)t=5,j geq 2t+ 1 andm geq 20 ; (5)t=5, j geq 2t+ 3 and12 leq m leq 19 ; (6)t=5, j geq 2t+ 5 and10 leq m leq 11 ; (7)t=5, j geq 2t + 7 andm=9 ; (8)t= 5, j geq 2t+ 9 andm = 8 . 相似文献
3.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1982,28(4):665-668
The modular distance induces a metric if and only if the nonadjacent form of the modulusM has one of the following forms:1) 2^{n}+2^{n-2} pm 2^{i} , wheren-igeq 4; 2) 2^{n} - 2^{j} pm 2^{i} , where2 leq n -j leq 5 andj-igeq 2; 3) 2^{n} pm 2^{j} , wheren -j geq 2; 4) 2^{n} . 相似文献
4.
5.
《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. 相似文献
6.
《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 . 相似文献
7.
On the distribution of de Bruijn sequences of given complexity 总被引:1,自引:0,他引:1
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1984,30(4):611-614
The distributiongamma (c, n) of de Bruijn sequences of ordern and linear complexityc is 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 3 such thatcn is even. 相似文献
8.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1967,13(1):91-94
The probability of a set of binaryn -tuples is defined to be the sum of the probabilities of the individualn -tuples when each digit is chosen independently with the same probabilityp of being a "one." It is shown that, under such a definition, the ratio between the probability of a subgroup of order2^{k} and any of its proper cosets is always greater than or equal to a functionF_{k}(p) , whereF_{k}(p) geq 1 forp leq frac{1}{2} with equality when and only whenp = frac{1}{2} . It is further shown thatF_{k}(p) is the greatest lower bound on this ratio, since a subgroup and proper coset of order2^{k} can always be found such that the ratio between their probabilities is exactlyF_{k}(p) . It is then demonstrated that for a linear code on a binary symmetric channel the "tall-zero" syndrome is more probable than any other syndrome. This result is applied to the problem of error propagation in convolutional codes. 相似文献
9.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1986,32(3):349-354
An(n, k, d) linear code overF= GF(q) is said to be {em maximum distance separable} (MDS) ifd = n - k + 1 . It is shown that an(n, k, n - k + 1) generalized Reed-Solomon code such that2leq k leq n - lfloor (q - 1)/2 rfloor (k neq 3 {rm if} q is even) can be extended by one digit while preserving the MDS property if and only if the resulting extended code is also a generalized Reed-Solomon code. It follows that a generalized Reed-Solomon code withk in the above range can be {em uniquely} extended to a maximal MDS code of lengthq + 1 , and that generalized Reed-Solomon codes of lengthq + 1 and dimension2leq k leq lfloor q/2 rfloor + 2 (k neq 3 {rm if} q is even) do not have MDS extensions. Hence, in cases where the(q + 1, k) MDS code is essentially unique,(n, k) MDS codes withn > q + 1 do not exist. 相似文献
10.
《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. 相似文献
11.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1981,27(1):132-136
A randomized decision rule is derived and proved to be the saddlepoint solution of the robust detection problem for known signals in independent unknown-mean amplitude-bounded noise. The saddlepoint solutionphi^{0} uses an equaUy likely mixed strategy to chose one ofN Bayesian single-threshold decision rulesphi_{i}^{0}, i = 1,cdots , N having been obtained previously by the author. These decision rules are also all optimal against the maximin (least-favorable) nonrandomized noise probability densityf_{0} , wheref_{0} is a picket fence function withN pickets on its domain. Thee pair(phi^{0}, f_{0}) is shown to satisfy the saddlepoint condition for probability of error, i.e.,P_{e}(phi^{0} , f) leq P_{e}(phi^{0} , f_{0}) leq P_{e}(phi, f_{0}) holds for allf andphi . The decision rulephi^{0} is also shown to be an eqoaliir rule, i.e.,P_{e}(phi^{0}, f ) = P_{e}(phi^{0},f_{0}) , for allf , with4^{-1} leq P_{e}(phi^{0},f_{0})=2^{-1}(1-N^{-1})leq2^{-1} , N geq 2 . Thus nature can force the communicator to use an {em optimal} randomized decision rule that generates a large probability of error and does not improve when less pernicious conditions prevail. 相似文献
12.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1970,16(6):745-751
In this paper, we establish the following result. Theorem:A_i , the number of codewords of weighti in the second-order binary Reed-Muller code of length2^m is given byA_i = 0 unlessi = 2^{m-1} or2^{m-1} pm 2^{m-l-j} , for somej, 0 leq j leq [m/2], A_0 = A_{2^m} = 1 , and begin{equation} begin{split} A_{2^{m-1} pm 2^{m-1-j}} = 2^{j(j+1)} &{frac{(2^m - 1) (2^{m-1} - 1 )}{4-1} } \ .&{frac{(2^{m-2} - 1)(2^{m-3} -1)}{4^2 - 1} } cdots \ .&{frac{(2^{m-2j+2} -1)(2^{m-2j+1} -1)}{4^j -1} } , \ & 1 leq j leq [m/2] \ end{split} end{equation} begin{equation} A_{2^{m-1}} = 2 { 2^{m(m+1)/2} - sum_{j=0}^{[m/2]} A_{2^{m-1} - 2^{m-1-j}} }. end{equation} 相似文献
13.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1986,32(6):768-775
It is shown that for each integerb geq 1 infinitely many optimum cyclicb -burst-correcting codes exist, i.e., codes whose lengthn , redundancyr , and burst-correcting capabilityb , satisfyn = 2^{r-b+1} - 1 . Some optimum codes forb = 3, 4 , and5 are also studied in detail. 相似文献
14.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1978,24(5):627-628
Upper bounds on the covering radius of binary codes are studied. In particular it is shown that the covering radiusr_{m} of the first-order Reed-Muller code of lenglh2^{m} satisfies2^{m-l}-2^{lceil m/2 rceil -1} r_{m} leq 2^{m-1}-2^{m/2-1} . 相似文献
15.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1969,15(3):408-413
It is shown that ifm neq 8, 12 andm > 6 , there are some binary primitive BCH codes (BCH codes in a narrow sense) of length2^{m} - 1 whose minimum weight is greater than the BCH bound. This gives a negative answer to the question posed by Peterson [1] of whether or not the BCH bound is always the actual minimum weight of a binary primitive BCH code. It is also shown that for any evenm geq 6 , there are some binary cyclic codes of length2^{m} - 1 that have more information digits than the primitive BCH codes of length2^{m} - 1 with the same minimum weight. 相似文献
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》1972,18(6):824-825
For1 leq i leq m - s- 2 and0 leq s leq m -2i , the intersection of the binary BCH code of designed distance2 ^{m-s-1} - 2 ^{m-s-t-1} - 1 and length2^m - 1 with the shortened(s + 2) th-order Reed-Muller code of length2^m -- 1 has codewords of weight2^{m-s-1} - 2^{m-s-t-1} - 1 . 相似文献
18.
《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. 相似文献
19.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1973,19(6):769-772
In this, the first part of a two-part paper, we establish a theorem concerning the entropy of a certain sequence of binary random variables. In the sequel we will apply this result to the solution of three problems in multi-user communication, two of which have been open for some time. Specifically we show the following. LetX andY be binary randomn -vectors, which are the input and output, respectively, of a binary symmetric channel with "crossover" probabilityp_0 . LetH{X} andH{ Y} be the entropies ofX andY , respectively. Then begin{equation} begin{split} frac{1}{n} H{X} geq h(alpha_0), qquad 0 leq alpha_0 &leq 1, Rightarrow \ qquad qquad &qquad frac{1}{n}H{Y} geq h(alpha_0(1 - p_0) + (1 - alpha_0)p_0) end{split} end{equation} whereh(lambda) = -lambda log lambda - (1 - lambda) log(l - lambda), 0 leq lambda leq 1 . 相似文献
20.
Bent-function sequences 总被引:12,自引:0,他引:12
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1982,28(6):858-864
In this paper we construct a new family of nonlinear binary signal sets which achieve Welch's lower bound on simultaneous cross correlation and autocorrelation magnitudes. Given a parametern withn=0 pmod{4} , the period of the sequences is2^{n}-1 , the number of sequences in the set is2^{n/2} , and the cross/auto correlation function has three values with magnitudesleq 2^{n/2}+1 . The equivalent linear span of the codes is bound above bysum_{i=1}^{n/4}left(stackrel{n}{i} right) . These new signal sets have the same size and correlation properties as the small set of Kasami codes, but they have important advantages for use in spread spectrum multiple access communications systems. First, the sequences are "balances," which represents only a slight advantage. Second, the sequence generators are easy to randomly initialize into any assigned code and hence can be rapidly "hopped" from sequence to sequence for code division multiple access operation. Most importantly, the codes are nonlinear in that the order of the linear difference equation satisfied by the sequence can be orders of magnitude larger than the number of memory elements in the generator that produced it. This high equivalent linear span assures that the code sequence cannot be readily analyzed by a sophisticated enemy and then used to neutralize the advantages of the spread spectrum processing. 相似文献