Coding Rate Analysis of Forbidden Overlap Codes in High-Speed Buses

Chang C., Cheng J., Huang T., Huang X., Lee D., Chen C.

The crosstalk effect is one of the main problems in deep sub-micron designs of high-speed buses. To mitigate the crosstalk effect, there are several types of crosstalk avoidance codes proposed in the literature. In this paper, we are particularly interested in generating forbidden transition codes that do not have opposite transitions on any two adjacent wires. For this, we propose a sequential bit-stuffing algorithm and a parallel bit-stuffing algorithm. For the sequential bit-stuffing algorithm, we perform a worst-case analysis and a probabilistic analysis. We show by both theoretic analysis and simulations that the coding rate of the sequential bit-stuffing encoding scheme is quite close to the Shannon capacity. In particular, for a bus with $n=10$ parallel wires, the difference is only 2.2 percent. Using a Markov chain analysis, we show that the coding rate of the parallel bit-stuffing algorithm is only slightly lower than that of the sequential bit-stuffing algorithm. The implementation complexity of the parallel bit-stuffing algorithm is linear with $n$ . In comparison with the existing forbidden transition codes that use the Fibonacci representation in the literature, our bit-stuffing algorithms not only achieve higher coding rates but also have much lower implementation complexity.

Mutyam M.

Propagation delay across long on-chip buses is significant when adjacent wires are transitioning in opposite direction (i.e., crosstalk transitions) as compared to transitioning in the same direction. By exploiting Fibonacci number system, we propose a family of Fibonacci coding techniques for crosstalk avoidance, relate them to some of the existing crosstalk avoidance techniques, and show how the encoding logic of one technique can be modified to generate codewords of the other technique.

Wu X., Yan Z.

Low-complexity CODECs for two classes of crosstalk avoidance codes (CACs), forbidden pattern codes (FPCs) and forbidden transition codes (FTCs), have been recently proposed based on Fibonacci-based binary numeral system. In this paper, we first generalize this idea and establish a generic framework for the CODEC design of all classes of CACs based on binary mixed-radix numeral systems. Using this framework, we then propose novel CODEC designs for three important classes of CACs, one lambda codes (OLCs), FPCs, and forbidden overlapping codes (FOCs). Our CODEC designs have area complexity and delay that increase quadratically with the size of the bus, while achieving optimal or nearly optimal code rates. Our CODECs also have simple and regular circuitry, and can easily achieve very high throughput by pipelining. Our efficient CODECs, used with such techniques as partial coding, help to make CACs a practical option in combating crosstalk delay, which is a bottleneck in deep submicrometer system-on-chip designs.

Duan C., Zhu C., Khatri S.P.

In this work, we present a CODEC design for the forbidden transition free crosstalk avoidance code. Our mapping and coding scheme is based on the Fibonacci numeral system and the mathematical analysis shows that all numbers can be represented by FTF vectors in the Fibonacci numeral system (FNS). The proposed CODEC design is highly efficient, modular and can be easily combined with a bus partitioning technique. We also investigate the implementation issues and our experimental results show that the proposed CODEC complexity is orders of magnitude better compared to the brute force implementation. Compared to the best existing approaches, we achieve a 17% improvement in logic complexity. A high speed design can be achieved through pipelining.

Cheng J., Chang C.-., Chao T.-., Lee D.-., Lien C.-.

Chou C.-., Chang C.-., Lee D.-., Cheng J.

In this paper, we prove a necessary and sufficient condition for the construction of 2-to-1 optical buffered first-in–first-out (FIFO) multiplexers by a single crossbar switch and fiber delay lines. We consider a feedback system consisting of an $(M+2)times (M+2)$ crossbar switch and $M$ fiber delay lines with delays $d_1, d_2,ldots, d_M$ . These $M$ fiber delay lines are connected from $M$ outputs of the crossbar switch back to $M$ inputs of the switch, leaving two inputs (respectively, two outputs) of the switch for the two inputs (respectively, two outputs) of the 2-to-1 multiplexer. The main contribution of this paper is the formal proof that $d_1=1$ and $d_i le d_i+1 le 2d_i$ , $i=1,2, ldots, M-1$ , is a necessary and sufficient condition on the delays $d_1, d_2,ldots,d_M$ for such a feedback system to be operated as a 2-to-1 FIFO multiplexer with buffer $sum _i=1^M d_i$ under a simple packet routing policy. Specifically, the routing of a packet is according to a specific decomposition of the packet delay, called the $cal C$ -transform in this paper. Our result shows that under such a feedback architecture a 2-to-1 FIFO multiplexer can be constructed with $M=O(log B)$ , where $B$ is the buffer size. Therefore, our construction improves on a more complicated construction recently proposed by Sarwate and Anantharam that requires $M=O(sqrt B)$ under the same feedback architecture (we note that their design is more general and works for priority queues).

Halevy S., Chen J., Roth R.M., Siegel P.H., Wolf J.K.

We derive lower bounds on the capacity of certain two-dimensional (2-D) constraints by considering bounds on the entropy of measures induced by bit-stuffing encoders. A more detailed analysis of a previously proposed bit-stuffing encoder for (d,/spl infin/)-runlength-limited (RLL) constraints on the square lattice yields improved lower bounds on the capacity for all d /spl ges/ 2. This encoding approach is extended to (d,/spl infin/)-RLL constraints on the hexagonal lattice, and a similar analysis yields lower bounds on the capacity for d /spl ges/ 2. For the hexagonal (1,/spl infin/)-RLL constraint, the exact coding ratio of the bit-stuffing encoder is calculated and is shown to be within 0.5% of the (known) capacity. Finally, a lower bound is presented on the coding ratio of a bit-stuffing encoder for the constraint on the square lattice where each bit is equal to at least one of its four closest neighbors, thereby providing a lower bound on the capacity of this constraint.

Cover T.M., Thomas J.A.

Preface to the Second Edition. Preface to the First Edition. Acknowledgments for the Second Edition. Acknowledgments for the First Edition. 1. Introduction and Preview. 1.1 Preview of the Book. 2. Entropy, Relative Entropy, and Mutual Information. 2.1 Entropy. 2.2 Joint Entropy and Conditional Entropy. 2.3 Relative Entropy and Mutual Information. 2.4 Relationship Between Entropy and Mutual Information. 2.5 Chain Rules for Entropy, Relative Entropy, and Mutual Information. 2.6 Jensen's Inequality and Its Consequences. 2.7 Log Sum Inequality and Its Applications. 2.8 Data-Processing Inequality. 2.9 Sufficient Statistics. 2.10 Fano's Inequality. Summary. Problems. Historical Notes. 3. Asymptotic Equipartition Property. 3.1 Asymptotic Equipartition Property Theorem. 3.2 Consequences of the AEP: Data Compression. 3.3 High-Probability Sets and the Typical Set. Summary. Problems. Historical Notes. 4. Entropy Rates of a Stochastic Process. 4.1 Markov Chains. 4.2 Entropy Rate. 4.3 Example: Entropy Rate of a Random Walk on a Weighted Graph. 4.4 Second Law of Thermodynamics. 4.5 Functions of Markov Chains. Summary. Problems. Historical Notes. 5. Data Compression. 5.1 Examples of Codes. 5.2 Kraft Inequality. 5.3 Optimal Codes. 5.4 Bounds on the Optimal Code Length. 5.5 Kraft Inequality for Uniquely Decodable Codes. 5.6 Huffman Codes. 5.7 Some Comments on Huffman Codes. 5.8 Optimality of Huffman Codes. 5.9 Shannon-Fano-Elias Coding. 5.10 Competitive Optimality of the Shannon Code. 5.11 Generation of Discrete Distributions from Fair Coins. Summary. Problems. Historical Notes. 6. Gambling and Data Compression. 6.1 The Horse Race. 6.2 Gambling and Side Information. 6.3 Dependent Horse Races and Entropy Rate. 6.4 The Entropy of English. 6.5 Data Compression and Gambling. 6.6 Gambling Estimate of the Entropy of English. Summary. Problems. Historical Notes. 7. Channel Capacity. 7.1 Examples of Channel Capacity. 7.2 Symmetric Channels. 7.3 Properties of Channel Capacity. 7.4 Preview of the Channel Coding Theorem. 7.5 Definitions. 7.6 Jointly Typical Sequences. 7.7 Channel Coding Theorem. 7.8 Zero-Error Codes. 7.9 Fano's Inequality and the Converse to the Coding Theorem. 7.10 Equality in the Converse to the Channel Coding Theorem. 7.11 Hamming Codes. 7.12 Feedback Capacity. 7.13 Source-Channel Separation Theorem. Summary. Problems. Historical Notes. 8. Differential Entropy. 8.1 Definitions. 8.2 AEP for Continuous Random Variables. 8.3 Relation of Differential Entropy to Discrete Entropy. 8.4 Joint and Conditional Differential Entropy. 8.5 Relative Entropy and Mutual Information. 8.6 Properties of Differential Entropy, Relative Entropy, and Mutual Information. Summary. Problems. Historical Notes. 9. Gaussian Channel. 9.1 Gaussian Channel: Definitions. 9.2 Converse to the Coding Theorem for Gaussian Channels. 9.3 Bandlimited Channels. 9.4 Parallel Gaussian Channels. 9.5 Channels with Colored Gaussian Noise. 9.6 Gaussian Channels with Feedback. Summary. Problems. Historical Notes. 10. Rate Distortion Theory. 10.1 Quantization. 10.2 Definitions. 10.3 Calculation of the Rate Distortion Function. 10.4 Converse to the Rate Distortion Theorem. 10.5 Achievability of the Rate Distortion Function. 10.6 Strongly Typical Sequences and Rate Distortion. 10.7 Characterization of the Rate Distortion Function. 10.8 Computation of Channel Capacity and the Rate Distortion Function. Summary. Problems. Historical Notes. 11. Information Theory and Statistics. 11.1 Method of Types. 11.2 Law of Large Numbers. 11.3 Universal Source Coding. 11.4 Large Deviation Theory. 11.5 Examples of Sanov's Theorem. 11.6 Conditional Limit Theorem. 11.7 Hypothesis Testing. 11.8 Chernoff-Stein Lemma. 11.9 Chernoff Information. 11.10 Fisher Information and the Cram-er-Rao Inequality. Summary. Problems. Historical Notes. 12. Maximum Entropy. 12.1 Maximum Entropy Distributions. 12.2 Examples. 12.3 Anomalous Maximum Entropy Problem. 12.4 Spectrum Estimation. 12.5 Entropy Rates of a Gaussian Process. 12.6 Burg's Maximum Entropy Theorem. Summary. Problems. Historical Notes. 13. Universal Source Coding. 13.1 Universal Codes and Channel Capacity. 13.2 Universal Coding for Binary Sequences. 13.3 Arithmetic Coding. 13.4 Lempel-Ziv Coding. 13.5 Optimality of Lempel-Ziv Algorithms. Compression. Summary. Problems. Historical Notes. 14. Kolmogorov Complexity. 14.1 Models of Computation. 14.2 Kolmogorov Complexity: Definitions and Examples. 14.3 Kolmogorov Complexity and Entropy. 14.4 Kolmogorov Complexity of Integers. 14.5 Algorithmically Random and Incompressible Sequences. 14.6 Universal Probability. 14.7 Kolmogorov complexity. 14.9 Universal Gambling. 14.10 Occam's Razor. 14.11 Kolmogorov Complexity and Universal Probability. 14.12 Kolmogorov Sufficient Statistic. 14.13 Minimum Description Length Principle. Summary. Problems. Historical Notes. 15. Network Information Theory. 15.1 Gaussian Multiple-User Channels. 15.2 Jointly Typical Sequences. 15.3 Multiple-Access Channel. 15.4 Encoding of Correlated Sources. 15.5 Duality Between Slepian-Wolf Encoding and Multiple-Access Channels. 15.6 Broadcast Channel. 15.7 Relay Channel. 15.8 Source Coding with Side Information. 15.9 Rate Distortion with Side Information. 15.10 General Multiterminal Networks. Summary. Problems. Historical Notes. 16. Information Theory and Portfolio Theory. 16.1 The Stock Market: Some Definitions. 16.2 Kuhn-Tucker Characterization of the Log-Optimal Portfolio. 16.3 Asymptotic Optimality of the Log-Optimal Portfolio. 16.4 Side Information and the Growth Rate. 16.5 Investment in Stationary Markets. 16.6 Competitive Optimality of the Log-Optimal Portfolio. 16.7 Universal Portfolios. 16.8 Shannon-McMillan-Breiman Theorem (General AEP). Summary. Problems. Historical Notes. 17. Inequalities in Information Theory. 17.1 Basic Inequalities of Information Theory. 17.2 Differential Entropy. 17.3 Bounds on Entropy and Relative Entropy. 17.4 Inequalities for Types. 17.5 Combinatorial Bounds on Entropy. 17.6 Entropy Rates of Subsets. 17.7 Entropy and Fisher Information. 17.8 Entropy Power Inequality and Brunn-Minkowski Inequality. 17.9 Inequalities for Determinants. 17.10 Inequalities for Ratios of Determinants. Summary. Problems. Historical Notes. Bibliography. List of Symbols. Index.

Moision B.E., Orlitsky A., Siegel P.H.

Certain magnetic recording applications call for a large number of sequences whose differences do not include certain disallowed binary patterns. We show that the number of such sequences increases exponentially with their length and that the growth rate, or capacity, is the logarithm of the joint spectral radius of an appropriately defined set of matrices. We derive a new algorithm for determining the joint spectral radius of sets of nonnegative matrices and combine it with existing algorithms to determine the capacity of several sets of disallowed differences that arise in practice.

Weeks W., Blahut R.E.

We define a checkerboard code as a two-dimensional binary code that satisfies some constraint, e.g., every binary one must be surrounded by eight zeros, and then investigate the capacity for each of several different constraints. Using a recursive construction we develop a series of loose bounds on the capacity. These bounds, in turn, lead to conjecturally precise estimates of the capacity by the use of a numerical convergence-speeding technique called Richardson extrapolation. Finally, using the value of the capacity, we define and compute a measure of coding gain which allows us to compare checkerboard codes to simple coding schemes.

Alexopoulos C., Seila A.F.

This paper reviews and evaluates strategies for implementing the batch means method for estimating the mean of a stationary simulation output process.

Orcutt E.K., Marcellin M.W.

Multitrack run-length-limited (d, k) modulation codes were recently introduced as a method to increase storage densities in magnetic and optical recording systems. These codes are a generalization of the usual run-length-limited (d, K) codes and provide for increased storage density by relaxing the k-constraint and encoding multiple tracks in parallel. Previously, n-track (d, K) codes used all n tracks to satisfy the K constraint causing synchronization to be completely intolerant of faulty tracks. The authors present multitrack (d, k) codes which allow for r faulty tracks by mandating that all subsets of n-r tracks satisfy the K constraint. >

Horn R.A., Johnson C.R.

Linear algebra and matrix theory are fundamental tools in mathematical and physical science, as well as fertile fields for research. This new edition of the acclaimed text presents results of both classic and recent matrix analyses using canonical forms as a unifying theme, and demonstrates their importance in a variety of applications. The authors have thoroughly revised, updated, and expanded on the first edition. The book opens with an extended summary of useful concepts and facts and includes numerous new topics and features, such as: - New sections on the singular value and CS decompositions - New applications of the Jordan canonical form - A new section on the Weyr canonical form - Expanded treatments of inverse problems and of block matrices - A central role for the Von Neumann trace theorem - A new appendix with a modern list of canonical forms for a pair of Hermitian matrices and for a symmetric-skew symmetric pair - Expanded index with more than 3,500 entries for easy reference - More than 1,100 problems and exercises, many with hints, to reinforce understanding and develop auxiliary themes such as finite-dimensional quantum systems, the compound and adjugate matrices, and the Loewner ellipsoid - A new appendix provides a collection of problem-solving hints.

Shannon C.E.

The recent development of various methods of modulation such as PCM and PPM which exchange bandwidth for signal-to-noise ratio has intensified the interest in a general theory of communication. A basis for such a theory is contained in the important papers of Nyquist 1 and Hartley 2 on this subject. In the present paper we will extend the theory to include a number of new factors, in particular the effect of noise in the channel, and the savings possible due to the statistical structure of the original message and due to the nature of the final destination of the information.

Shirmohammadi Z., Taali M.

Hosseini Omshi M.S., Faghih Mirzaee R., Reza A., Mirzaei M.

Taali M., Shirmohammadi Z., Danish M.S., Khosravy M.

Capacitive coupling and inductive coupling are the two main factors in the occurrence of crosstalk fault in the communication bus. Among the various methods for reducing crosstalk fault, Crosstalk Avoidance Codes (CAC) codes are effective. However, with technology scaling, CACs are not able to prevent inductive effects. The proposed CACs methods are mainly based on capacitive coupling and do not consider inductive effects. To overcome this issue, a coding method is presented to avoid crosstalk fault called Joint Capacitive and Inductive CAC (JCI-CAC). The JCI-CAC coding reduces crosstalk faults by removing patterns of inductive coupling as $'11111'$ and $'00000'$ and capacitive coupling as $'10101'$ and $'01010'$ . The JCI-CAC offers a new method to generate a new numerical system for data encoding that has a low computational overhead so that it can be used for any desired width of the communication bus. The simulation results of the proposed JCI-CAC mechanism are investigated in different criteria of delay, power consumption and area overhead. The simulation results provide less power consumption in JCI-CAC than other recent approaches. There have also been improvements in overhead area and critical paths in JCI-CAC coding. The main novelty of this paper is to provide a new numerical system and a new coding algorithm with minimum cell area overhead and power consumption, considering inductance coupling in addition to capacitive coupling. Based on simulation results, power consumption of JCI-CAC in the 8-bit and 16-bit bus is reduced by up to 20% compared to SOTA and FPF (PS-Fibo, S2AP, Improved Fibo-CAC, Fibo-CAC) codings. Also, cell area overhead in JCI-CAC compared to SOTA coding in an 8-bit bus is reduced by 4.8%.

Taali M., Shirmohammadi Z.

Crosstalk fault on the chip wires seriously jeopardizes data reliability. One of the most effective methods to reduce crosstalk fault is crosstalk fault avoidance coding (CAC) based on numeral systems. CAC methods reduce crosstalk fault by preventing certain transitions from occurring. Improved One-Lambda Coding (IOLC) demonstrates the best performance among all types of CAC methods since it shows the least delay and area occupancy overhead. However, designers of larger-width buses need a systematic framework for generating cost-effective Improved One-Lambda Codes (IOLC). Such a framework should have two distinctive features: Firstly, it should specify the number of code words in each particular width, which is referred to as cardinality. Secondly, it should provide an algorithm for producing complete and unambiguous numeral systems. In this paper, the following items have been provided to achieve these two features. 1) A recursive formula called recursive symmetry has been proposed to determine the extent of cardinality for Improved One-Lambda Coding. 2) Using the recursive symmetry formula, an algorithm has been developed to generate different numeral systems for Improved One-Lambda Coding. The evaluation results showed that sending code words through the Improved One-Lambda Coding method using our proposed algorithm improves the status of delay in the worst cases