Data Transportation and Protection

1. Data—Its Representation and Manipulation.- 1.1. Introduction.- 1.2. Number Systems.- 1.3. Negabinary Numbers.- 1.4. The Factorial Number System.- 1.5. The Gray Code.- 1.6. A Look at Boolean Functions.- References.- 2. Counting and Probability.- 2.1. Counting.- 2.2. Generating Functions.- 2.3. Permutations.- 2.3.1. Generation of Permutations.- 2.4. Combinations.- 2.4.1. Combinatorial Identities.- 2.4.2. Combinatorial Tables.- 2.5. Recurrence Relations/Difference Equations.- 2.6. Probability.- 2.7. Generating Functions in Probability Theory.- 2.8. The Bernoulli Source.- 2.9. Some Important and Famous Problems.- 2.10. Random Mappings.- 2.11. Redundancy and the Perfect Voter.- 2.12. Bias.- 2.13. Maximum Likelihood Estimation.- References.- 3. The Natural Numbers and Their Primes.- 3.1. Introduction.- 3.2. Finding Primes: I.- 3.2.1. The Sieve of Eratosthenes.- 3.2.2. Number of Primes and Their Distribution.- 3.3. The Euclidean Algorithm.- 3.4. Congruences.- 3.5. Residue Sets.- 3.6. Reduced Residue Sets.- 3.7. The Euler-Fermat Theorem.- 3.8. Wilson’s Theorem.- 3.9. The Function ?.- 3.9.1. Fermat’s (Little) Theorem.- 3.10. Another Number Theoretic Function and the Concept of “Square-Free”.- 3.11. The Möbius Inversion Formula.- 3.12. Primitive Roots.- 3.13. The Inverse Problem—Finding Discrete Logarithms.- 3.13.1. An Example of the Split-Search Algorithm.- 3.14. The Chinese Remainder Theorem.- 3.15. Finding Primes: II.- 3.15.1. A Probabilistic Extension (Rabin, 1980).- 3.15.2. Building Large Primes.- References.- 4. Basic Concepts in Matrix Theory.- 4.1. Introduction.- 4.2. Concept of a Field and a Group.- 4.3. Basic Definitions.- 4.4. Matrix Operations.- 4.4.1. Matrix Multiplication.- 4.4.2. Determinants.- 4.4.3. Finite Field Matrix Operations.- 4.5. Partitioned Matrices.- 4.5.1. Direct Sum of Matrices.- 4.5.2. Connectivity in Terms of Matrices.- 4.6. Inverses of Matrices.- 4.6.1. Inverses Using Elementary Operations.- 4.6.2. Elementary Row Operations.- 4.6.3. Elementary Matrices.- 4.6.4. Inversion Using Partitioned Matrices.- 4.6.5. A Useful Factorization of a Matrix.- References.- 5. Matrix Equations and Transformations.- 5.1. Introduction.- 5.2. Linear Vector Spaces.- 5.2.1. Rank of Matrices.- 5.3. Gram-Schmidt Process.- 5.4. Solutions of Equations.- 5.4.1. Solutions Using Elementary Operations.- 5.4.2. The Fundamental Theorem.- 5.4.3. Solutions of Homogeneous Equations.- 5.5. Solutions of Overdetermined Systems.- 5.5.1. Iteratively Reweighted Least Squares (IRLS) Algorithm.- 5.5.2. Residual Steepest Descent (RSD) Algorithm.- 5.5.3. Solutions of Equations that Involve Toeplitz Matrices.- 5.5.4. Durbin’s Algorithm.- 5.5.5. Levinson’s Algorithm.- 5.6. Normal Matrices.- 5.6.1. Use of Symmetric Matrices in Testing the Property of Positive Definite and Semidefinite Matrices.- 5.7. Discrete Transforms.- 5.7.1. Discrete Fourier Transform (DFT).- 5.7.2. Bit Reversion.- 5.7.3. Discrete Cosine Transform (DCT).- 5.7.4. Walsh-Hadamard Transform.- 5.7.5. Kronecker Products.- 5.7.6. Use of the Matrix A in (143) for DFT Implementation.- 5.7.7. An Example of a Number Theoretic Transform (NTT) (Agarwal and Burrus, 1975).- References.- 6. Matrix Representations.- 6.1. Introduction.- 6.2. Eigenvalue Problem.- 6.3. Diagonal Representation of Normal Matrices.- 6.4. Representations of Nondiagonable Matrices.- 6.4.1. Jordan Matrix.- 6.5. Circulant Matrix and Its Eigenvectors.- 6.6. Simple Functions of Matrices.- 6.7. Singular Value Decomposition.- 6.8. Characteristic Polynomials.- 6.9. Minimal Polynomial.- 6.10. Powers of Some Special Matrices.- 6.10.1. Idempotent Matrices.- 6.10.2. Nilpotent Matrices.- 6.10.3. Involutory Matrices.- 6.10.4. Roots of Identity Matrices.- 6.11. Matrix Norms.- 6.11.1. A Simple Iterative Method for Finding ?(A).- References.- 7. Applications of Matrices to Discrete Data System Analysis.- 7.1. Introduction.- 7.2. Discrete Systems.- 7.2.1. Linear Shift-Invariant Systems.- 7.2.2. Characterization of a Linear System.- 7.3. Discrete Convolution.- 7.3.1. Discrete Correlation.- 7.3.2. FFT Computation of Convolutions.- 7.3.3. Applications of Number Theoretic Transforms to Convolution.- 7.4. Discrete Deconvolution.- 7.5. Linear Constant-Coefficient Difference Equations.- 7.6. Matrix Representation of an Nth-Order Constant-Coefficient Difference Equation.- 7.7. Solutions of an Nth-Order Difference Equation Using a State Model Representation.- 7.7.1. Computation of q(0).- 7.7.2. Initial Conditions.- 7.7.3. State Equations—Some Generalizations.- 7.8. Transfer Functions: An Introduction to Z Transforms.- 7.9. Observability Problem.- References.- 8. Random and Pseudorandom Sequences.- 8.1. Introduction.- 8.2. Markov Chains.- 8.3. m-Sequences (Hershey, 1982).- 8.3.1. Special Purpose Architectures.- 8.3.2. The Shift and Add Property.- 8.3.3. Phase Shifts and the Delay Operator Calculus.- 8.3.4. Large Phase Shifts and the Art of Exponentiation.- 8.3.5. Decimation.- 8.3.6. Decimation by a Power of 2.- 8.3.7. General Decimation.- 8.3.8. Inverse Decimation.- 8.3.9. Generation of High-Speed m-Sequences.- 8.3.10. On Approximating a Bernoulli Source with an m-Sequence.- References.- 9. Source Encoding.- 9.1. Introduction.- 9.2. Generalized Bernoulli Source.- 9.3. Unique Decodability.- 9.3.1. A Basic Inequality Required by Unique Decodability.- 9.3.2. Comma-Free Codes.- 9.4. Synchronizable Codes.- 9.5. Information Content of a Bernoulli Source.- 9.6. The Huffman Code.- 9.6.1. Connell’s Method of Coding.- 9.7. Source Extension and Its Coding.- 9.8. Run Length Encoding.- 9.9. Encoding to a Fidelity Criterion.- References.- 10. Information Protection.- 10.1. Classical Cryptography.- 10.1.1. The DES.- 10.1.2. Modes of the DES.- 10.2. Public Key Cryptography.- 10.2.1. Merkle’s Puzzle.- 10.2.2. Public Key Cryptography and Its Pitfalls: The Diffie-Hellman System.- 10.2.3. The RSA System.- 10.2.4. A Faulty Implementation Protocol for the RSA.- 10.3. Secret Sharing Systems.- 10.3.1. Matrix Construction for Secret Sharing Systems.- References.- 11. Synchronization.- 11.1. Introduction.- 11.2. Epoch Synchronization.- 11.2.1. Autocorrelation.- 11.2.2. Bit Sense Known.- 11.2.3. Bit Sense Unknown.- 11.3. Phase Synchronization.- 11.3.1. m-Sequence Synchronization.- 11.3.2. Polynomial Known: Errorless Reception.- 11.3.3. Polynomial Known: Errors in Reception.- 11.3.4. Polynomial Unknown: Errorless Reception.- 11.3.5. Rapid Acquisition Sequences.- 11.3.6. The Thue-Morse Sequence.- 11.3.7. A Statistical Property of the TMS.- 11.3.8. Use of the TMS for Synchronization.- 11.3.9. Titsworth’s Component Codes.- References.- 12. The Channel and Error Control.- 12.1. Introduction.- 12.2. A Channel Model.- 12.2.1. Combinatorial Solution.- 12.2.2. Solution by Difference Equations.- 12.2.3. Solution by Markov Processes.- 12.3. The Simplest Hamming Code.- 12.4. The Hamming Code—Another Look.- 12.5. The z-Channel and a Curious Result.- 12.5.1. Strategy I.- 12.5.2. Strategy II.- 12.5.3. Strategy III.- 12.6. The Data Frame Concept.- 12.6.1. The Error Check Field and the CRC.- 12.7. A Curious Problem.- 12.8. Estimation of Channel Parameters.- References.- 13. Space Division Connecting Networks.- 13.1. Introduction.- 13.2. Complete Permutation Networks.- 13.2.1. The Crossbar.- 13.3. The Clos Network.- 13.4. A Rearrangeable Connecting Network and Paull’s Algorithm.- 13.5. The Perfect Shuffle and the Omega Network.- 13.6. The Beneš-Waksman Permutation Network.- 13.7. The Perfect Shuffle Network Revisited.- References.- 14. Network Reliability and Survivability.- References.