Design of some new efficient balanced codes

A balanced code with r check bits and k information bits is a binary code of length k+r and cardinality 2^k such that each codeword is balanced; that is, it has [(k+r)/2] 1's and [(k+r)/2] 0's. This paper contains new methods to construct efficient balanced codes. To design a balanced code, an information word with a low number of 1's or 0's is compressed and then balanced using the saved space. On the other hand, an information word having almost the same number of 1's and 0's is encoded using the single maps defined by Knuth's (1986) complementation method. Three different constructions are presented. Balanced codes with r check bits and k information bits with k⩽2^r+1-2, k⩽3×2^r-8, and k⩽5×2^r-10r+c(r), c(r)∈{-15, -10, -5, 0, +5}, are given, improving the constructions found in the literature. In some cases, the first two constructions have a parallel coding scheme     

Tight upper bounds on the redundancy of Huffman codes

Bounds on the redundancy of Huffman codes in terms of the probability p₁ of the most likely source letter are provided. In particular, upper bounds are presented that are sharper than the bounds given recently by R.G. Gallager (ibid., vol.IT-24, no.6, p.668-74, Nov.1978) and by R.M. Capocelli et al. (ibid., vol. IT-32, no.6, p.854-857, Nov. 1986) for an interval 2/(2^l+1+1)<p₁<1/(2^l-1), l⩾2. It is shown that the new bounds are the tightest possible for these intervals     

Binary prefix codes ending in a “1”

Binary prefix codes with the constraint that each codeword must end with a “1” have been recently introduced by Berger and Yeung (1990). We analyze the performance of such codes by investigating their average codeword length. In particular, we show that a very simple strategy permits the construction of a “1”-ended binary prefix code whose average codeword length is less than H+1 for any discrete source with entropy H. We also prove a tight lower bound on the optimal average codeword length in terms of H and of the minimum letter probability of the source. Finally, we discuss the problem of finding an optimum feasible code     

Bounds on the entropy series

Upper bounds on the entropy of a countable integer-valued random variable are furnished in terms of the expectation of the logarithm function. In particular, an upper bound is derived that is sharper than that of P. Elias (ibid., vol.IT-21, no.2, p.194-203, 1975), for all values of E_p(log). Bounds that are better only for large values of E_p than the previous known upper bounds are also provided     

On the characterization of statistically synchronizablevariable-length codes

The authors consider statistically synchronizable variable-length codes, i.e. codes that admit decoders able to self-synchronize with high probability if the input sequence of code symbols is long enough. They show that a necessary and sufficient condition for the existence of a statistically self-synchronizing decoder and, therefore, for a code to be statistically synchronizable, is that the code has a synchronizing sequence. They also give a decision procedure to test whether a code has a synchronizing sequence. Finally, they specialize the procedure to obtain a simple and efficient algorithm to test the statistical synchronizability property of prefix codes     

A note on D-ary Huffman codes

An upper bound on the redundancy of D-ary Huffman codes in terms of the probability p₁ of the most likely source letter is provided. For large values of p₁, the bound improves the one given by R.G. Gallager (1978). Additionally, some results known for the binary case (D=2) are extended to arbitrary D-ary Huffman codes. As a consequence, a tight lower bound that corrects a bound recently proposed by J.D. Golic and M.M. Obradovic (1987) is derived     

Selective membrane application for the industrial one-step DME production process fed by CO2 rich streams: Modeling and simulation

The integration of a microporous zeolite membrane, highly selective to steam water in a one-step DME synthesis reactor, is modeled and assessed. The membrane reactor performance and the comparison with a conventional reactor, are studied mainly for a CO₂-rich feedstock, i.e. derived from a biogas-derived syngas. The continuous removal of water from the reaction environment reduces the inhibition effect of H₂O on the CO₂ hydrogenation and methanol dehydration reactions, thus allowing the achievement of high conversions, DME yield and selectivity even at large CO₂ composition in the inlet feedstock. If a CO₂/CO ratio equal to 3 is imposed in the inlet stream, the DME yield reaches a value of 0.75 vs. 0.57 in a conventional reactor operating at the same conditions, the X_COx and X_CO2 are 0.75 and 0.69, with an improvement of 15.4% and 30.2%, and the DME selectivity is close to 1.The membrane reactor behavior is assessed by a one-dimensional, non-isothermal model. Fixing industrial scale parameters, the effect of the main operating conditions as temperature and pressure in the reactor environment, the Gas Hourly Space Velocity (GHSV), the feedstock composition in terms of CO₂/CO and H₂/CO_x ratios, the pressure and flow rate downstream to the selective membrane are analyzed and discussed.The simulations confirm the improvement of the reactor performance, within large ranges of operating conditions, derived from the integration of the selective membrane. On this basis, membrane reactor for one-step DME synthesis process can be included in the “CO₂ valorization” framework since the greenhouse gas CO₂ can be used as a reactant in an industrial process and thus converted into a useful and marketable product.     

On the size of shares for secret sharing schemes

A secret sharing scheme permits a secret to be shared among participants in such a way that only qualified subsets of participants can recover the secret, but any nonqualified subset has absolutely no information on the secret. The set of all qualified subsets defines the access structure to the secret. Sharing schemes are useful in the management of cryptographic keys and in multiparty secure protocols.We analyze the relationships among the entropies of the sample spaces from which the shares and the secret are chosen. We show that there are access structures with four participants for which any secret sharing scheme must give to a participant a share at least 50% greater than the secret size. This is the first proof that there exist access structures for which the best achievable information rate (i.e., the ratio between the size of the secret and that of the largest share) is bounded away from 1. The bound is the best possible, as we construct a secret sharing scheme for the above access structures that meets the bound with equality.This work was partially supported by Algoritmi, Modelli di Calcolo e Sistemi Informativi of M.U.R.S.T. and by Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo of C.N.R. under Grant Number 91.00939.PF69.     

An efficient algorithm for testing immutability of variable-lengthcodes

Immutable codes, which have recently been introduced as a tool for preventing undesirable changes of data recorded over write-once memories, are considered. The have the property that any change of recorded information over such memories can be detected. A fast algorithm for testing whether a variable-length code is immutable is presented. The complexity of the algorithm is O(L²), where L is the sum of the codeword lengths