Embedded method for indexing control arrays in multimode conservative codes for holographic storage

In multimode conservative codes for holographic storage, an unconstrained m x n binary array S of source data is added to a set of (m + 1)(n + 1) control arrays to form the selection set, which is guaranteed to contain at least one conservative array of strength at least t, such that each row and each column of the output array contain at least t transitions. To be able to retrieve the original source data array S during the decoding process, at least[log2(m + 1)(n + 1)]redundant bits are necessary to index the (m + 1)(n + 1) control arrays. Presented is a method for embedding the index information of the control arrays into the encoded arrays in a manner which requires only [log2(m + 1)]+[log2(n + 1)]redundant bits, thereby attaining high coding efficiency.     

Some Remarks on BCH Bounds and Minimum Weights of Binary Primitive BCH Codes

It is shown that ifm neq 8, 12andm > 6, there are some binary primitive BCH codes (BCH codes in a narrow sense) of length2^{m} - 1whose 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} - 1that have more information digits than the primitive BCH codes of length2^{m} - 1with the same minimum weight.     

有限域GF(2~m)上的一个新的求逆算法

根据有限域GF(2~m)上的正规基表示和Massey-Omura乘法器,本文提出了一个复杂性为O(logm)的求逆算法。新算法完成一次求逆运算只需要[log22(m-1)]+w(m-1)-1次乘法和m-1次循环移位,这里[x]表示小于等于x的最大整数,w(m-1)表示m-1的二进制表示中“1”的个数。     

二元最佳低相关区序列集构造法

基于周期为2m-1的二元伪随机序列,利用交织法构造了一类满足一定条件的周期为2m+1-1的基序列集,进而利用这些基序列集构造得到了一类参数达到Tang-Fan-Matsufuji界的二元最佳低相关区序列集。这类低相关区序列集具有更多的序列数目,应用到准同步CDMA系统可以支持更多的用户。     

Fault detection for multiple-valued logic circuits with fanout-free

The single fault and multiple fault detections for multiple-valued logic circuits are studied in this paper. Firstly, it is shown that the cardinality of optimal single fault test set for fanout-free m-valued circuits with n primary inputs is not more than n + 1, for linear tree circuits is two, and for multiplication modulo circuits is two if n is an odd number or if n is an even number and m > 3, where the optimal test set of a circuit has minimal number of test vectors. Secondly, it is indicated that the cardinality of optimal multiple fault test set for linear tree circuits with n primary inputs is 1 + [n/(m - 1)], for multiplication modulo circuits is n + 1, for fanout-free circuits that consist of 2-input linear tree circuits and 2-input multiplication modulo circuits is not greater than n+ 1, where [x] denotes the smallest integer greater than or equal to x. Finally, the single fault location approaches of linear tree circuits and multiplication modulo circuits are presented, and all faults in th     

Ultrasound Dosage for Nontherapeutic Use on Human Beings? Extrapolations from a Literature Survey

A practical method for analyzing the biological effects of nontherapeutic ultrasound was applied to the data of 21 different principal investigators. The data were compiled so that individual investigators could develop tentative guidelines of their own regarding the hazards of diagnostic ultrasound in human beings. One set of guidelines developed suggested that exposures of minimal hazard lie below a log/log line connecting 100 ?s of 100 W/cm2 ultrasound with 200 s of 100 mW/cm2 ultrasound. An ultrasonic intensity of 100 mW/cm2 or less was of little or no hazard for at least 10 000 s. These guidelines applied to both continuous- and pulsed-wave ultrasound doses that were described by average intensity multiplied by total exposure time. The proposed schedule was valid for 0.5-15 MHz and for all anatomic sites except the eyes.     

Two-dimensional weight-constrained codes through enumeration bounds

For a rational α∈(0,1), let 𝒜_n×m,α be the set of binary n×m arrays in which each row has Hamming weight αm and each column has Hamming weight αn, where αm and αn are integers. (The special case of two-dimensional balanced arrays corresponds to α=1/2 and even values for n and m.) The redundancy of 𝒜_n×m,α is defined by ρ_n×m,α=nmH(α)-log₂|𝒜 _n×m,α| where H(x)=-xlog₂x-(1-x)log₂(1-x). Bounds on ρ_n×m,α are obtained in terms of the redundancies of the sets 𝒜_ℒ,α of all binary ℒ-vectors with Hamming weight αℒ, ℒ∈{n,m}. Specifically, it is shown that ρ_n×m,α⩽nρ_m,α+mρ _n,α where ρ_ℒ,α=ℒH(α)-log₂|𝒜 _ℒ,α| and that this bound is tight up to an additive term O(n+log m). A polynomial-time coding algorithm is presented that maps unconstrained input sequences into 𝒜_n×m,α at a rate H(α)-(ρ_m,α/m)     

An upper bound on run-length coding entropy

A method of calculating the maximum entropy per run in binary run-length coding is given when run length is limited to a maximum of M. It is also shown that Huang's bound [1] can be obtained from the present result as M tends to infinity.     

New Optimal [36,13,12] Code and its Construction

This paper presents a new optimal [36,13,12] binary linear block code which reaches the upper bound in [1] for best known binary linear block codes and its construction. It has a symmetric weight spectrum different to the known [36,13,12] codes constructed from the Morii [37,14,12] code [2] by shortening.     

Easily testable sequential machines with extra inputs and extra outputs

In a recent paper, Fujiwara et al. presented an efficient procedure for designing checking experiments for sequential machines. In this procedure any arbitrary sequential machine is augmented to an easily testable machine by adding only two special input symbols to the original machine. An easily testable machine is defined by the authors as a reduced and strongly connected machine which possesses a distinguishing sequence as well as a synchronising sequence of length [log2 q], and a transfer sequence with a length that is at most [log2 q] to take the machine from a specific state S1, to a state St for all i, where q is the number of machine states, and [r] denotes the smallest integer greater than or equal to r. For a q-state, p-input symbol easily testable machine, the authors' procedure provides an upper bound on the length of the checking experiment that approximately equals pq[log2 q]. Furthermore, the entire checking experiment happens to be preset. This letter reports an extension of the aforementioned work of Fujiwara et al. In the procedure developed through this extension, any arbitrary sequential machine is augmented to an easily testable machine, by adding not two special input symbols alone, but simultaneously adding [log2 q] output terminals to the original machine. This modification gives a reduced upper bound on the lengths of the checking experiments, and also permits coverage of fault types that may cause an increase in the number of machine states.     

New Design of Low-Correlation Zone Sequence Sets

In this paper, we present several construction methods for low-correlation zone (LCZ) sequence sets. First, we propose a design scheme for binary LCZ sequence sets with parameters (2ⁿ⁺¹-2,M,L,2). In this scheme, we can freely set the LCZ length L and the resulting LCZ sequence sets have the size M, which is almost optimal with respect to Tang, Fan, and Matsufuji bound. Second, given a q-ary LCZ sequence set with parameters (N,M,L,epsi) and even q, we construct another q-ary LCZ sequence set with parameters (2N,2M,L,2epsi) or (2N,2M,L-1,2epsi). Especially, the new set with parameters (2N,2M,L,2) can be optimal in terms of the set size if a q-ary optimal LCZ sequence set with parameters (N,M,L,1) is used     

An achievable bound for optimal noiseless coding of a random variable (Corresp.)

For a discreteN-valued random variable (Npossibly denumerably infinite) Leung-Yan-Cheong and Cover have given bounds for the minimal expected length of a one-to-one (not necessarily uniquely decodable) codeL_{1:1}=sum_{i=1}^{N} p_{i} log left( frac{1}{2} + 1 right).It is shown that the best possible case occurs for certain denumerably infinite sets of nonzero probabilities. This absolute bound is related to the Shannon entropyHof the distribution by(h (cdot)is the binary entropy function).     

An upper bound on the entropy of run-length coding (Corresp.)

An upper bound on the entropy per run in binary run-length coding isa loga - (a - 1)log (a - 1), whereais the average run length. This upper bound is attained by a time-quantized Poisson square wave.     

Efficient burst-correcting cyclic codes

A class of single burst error-correcting cyclic codes is introduced. The binary version of these codes has block length n = 2m ? 1, number of parity check digits n ? k = 2m?1, and correct bursts of length b = 2m?2, where m is an integer. These codes achieve the upper bound b ?(n ? k)/2, and normally have more information digits than interleaved codes of the same burst-correcting power. The multilevel case is also treated in the letter.     

Sequential diagnosis of processor array systems

We examine the diagnosis of processor array systems formed as two-dimensional arrays, with boundaries, and either four or eight neighbors for each interior processor. We employ a parallel test schedule. Neighboring processors test each other, and report the results. Our diagnostic objective is to find a fault-free processor or set of processors. The system may then be sequentially diagnosed by repairing those processors tested faulty according to the identified fault-free set, or a job may be run on the identified fault-free processors. We establish an upper bound on the maximum number of faults which can be sustained without invalidating the test results under worst case conditions. We give test schedules and diagnostic algorithms which meet the upper bound as far as the highest order term. We compare these near optimal diagnostic algorithms to alternative algorithms, both new and already in the literature, and against an upper bound ideal case algorithm, which is not necessarily practically realizable. For eight-way array systems with N processors, an ideal algorithm has diagnosability 3N/sup 2/3/-2N/sup 1/2/ plus lower-order terms. No algorithm exists which can exceed this. We give an algorithm which starts with tests on diagonally connected processors, and which achieves approximately this diagnosability. So the given algorithm is optimal to within the two most significant terms of the maximum diagnosability. Similarly, for four-way array systems with N processors, no algorithm can have diagnosability exceeding 3N/sup 2/3//2/sup 1/3/-2N/sup 1/2/ plus lower-order terms. And we give an algorithm which begins with tests arranged in a zigzag pattern, one consisting of pairing nodes for tests in two different directions in two consecutive test stages; this algorithm achieves diagnosability (3/2)(5/2)/sup 1/3/N/sup 2/3/-(5/4)N/sup 1/2/ plus lower-order terms, which is about 0.85 of the upper bound due to an ideal algorithm.     

Universal variable-to-fixed length source codes

A universal variable-to-fixed length algorithm for binary memoryless sources which converges to the entropy of the source at the optimal rate is known. We study the problem of universal variable-to-fixed length coding for the class of Markov sources with finite alphabets. We give an upper bound on the performance of the code for large dictionary sizes and show that the code is optimal in the sense that no codes exist that have better asymptotic performance. The optimal redundancy is shown to be H log log M/log M where H is the entropy rate of the source and M is the code size. This result is analogous to Rissanen's (1984) result for fixed-to-variable length codes. We investigate the performance of a variable-to-fixed coding method which does not need to store the dictionaries, either at the coder or the decoder. We also consider the performance of both these source codes on individual sequences. For individual sequences we bound the performance in terms of the best code length achievable by a class of coders. All the codes that we consider are prefix-free and complete     

On the norm and covering radius of the first-order Reed-Mullercodes

Let ρ(1,m) and N(1,m) be the covering radius and norm of the first-order Reed-Muller code R(1,m), respectively. It is known that ρ(1,2k+1)⩽lower bound [2^2k-2^(2k-1/2)] and N(1,2k+1)⩽2 lower bound [2^2k-2^(2k-1/2)] (k>0). We prove that ρ(1,2k+1)⩽2 lower bound [2^2k-1-2^(2k-3/2)] and N(1,2k+1)⩽4 lower bound [2^2k-1-2^(2k-3/2)] (k>0). We also discuss the connections of the two new bounds with other coding theoretic problems     

Rates of convergence in the source coding theorem, in empiricalquantizer design, and in universal lossy source coding

Rate of convergence results are established for vector quantization. Convergence rates are given for an increasing vector dimension and/or an increasing training set size. In particular, the following results are shown for memoryless real-valued sources with bounded support at transmission rate R. (1) If a vector quantizer with fixed dimension k is designed to minimize the empirical mean-square error (MSE) with respect to m training vectors, then its MSE for the true source converges in expectation and almost surely to the minimum possible MSE as O(√(log m/m)). (2) The MSE of an optimal k-dimensional vector quantizer for the true source converges, as the dimension grows, to the distortion-rate function D(R) as O(√(log k/k)). (3) There exists a fixed-rate universal lossy source coding scheme whose per-letter MSE on a real-valued source samples converges in expectation and almost surely to the distortion-rate function D(R) as O((√(loglog n/log n)). (4) Consider a training set of n real-valued source samples blocked into vectors of dimension k, and a k-dimension vector quantizer designed to minimize the empirical MSE with respect to the m=[n/k] training vectors. Then the per-letter MSE of this quantizer for the true source converges in expectation and almost surely to the distortion-rate function D(R) as O(√(log log n/log n))), if one chooses k=[(1/R)(1-ϵ)log n] for any ϵ∈(0.1)     

Optimal information-dispersal for increasing the reliability of adistributed service

This paper investigates the (m,n) information dispersal scheme (IDS) used to support fault-tolerant distributed servers in a distributed system. In an (m,n)-IDS, a file M is broken into n pieces such that any m pieces collected suffice for reconstructing M. The reliability of an (m,n)-IDS is primarily determined by 3 important factors: n=information dispersal degree (IDD), n/m=information expansion ratio (IER), P_s=success-probability of acquiring a correct piece. It is difficult to determine the optimal IDS with the highest reliability from very many choices. Our analysis shows: several novel features of (m,n)-IDS which can help reduce the complexity of finding the optimal IDS with the highest reliability; that an IDS with a higher IER might not have a higher reliability, even when P_s→1. Based on the theorems given herein, we have developed a method that reduces the complexity for computing the highest reliability from, O(ν) [ν=number of servers] to O(1) when the `upper bound of the IER'=1, or O(ν<sup>2</sup>) to O(1) when the `upper bound of the IER'>1     

Binary [18,11]2 codes do not exist-Nor do [64,53]2 codes

A binary, linear block code C with block length n and dimension n is commonly denoted by [n, k] or, if its minimum distance is d, by [n, k,d]. The code's covering radius r(C) can be defined as the smallest number r such that any binary column vector of length (n-k) can be written as a sum of r or fewer columns of a parity-check matrix of C. An [n,k] code with covering radius r is denoted by [n,k]r. R.A. Brualdi et al., (1989) showed that l(m,r) is defined to be the smallest n such that an [n,n-m]r code exists. l(m,2) is known for m⩽6, while it is shown by Brualdi et al. that 17⩽l(7,2)⩽19. This lower bound is improved by A.R. Calderbank et al. (1988), where it is shown that [17,10]2 codes do not exist. The nonexistence of [18,11]2 codes is proved, so that l(7,2)=19. l[7.2)=19 is established by showing that [18,11]2 codes do not exist. It is also shown that [64,53]2 codes do not exist, implying that l(11,2)⩾65