Data Transportation and Protection

ISBN-13: 9781461292906 / Angielski / Miękka / 2011 / 508 str.

John E. Hershey; Rao K. Yarlagadda; John E. Hershey

Opis

A new breed of engineer is developing in our contemporary society. These engineers are concerned with communications and computers, economics and regulation. These new engineers apply themselves to data-to its pack aging, transmission, and protection. They are data engineers. Formal curricula do not yet exist for their dedicated development. Rather they learn most of their tools "on the job" and their roots are in computer engineering, communications engineering, and applied mathe matics. There is a need to draw relevant material together and present it so that those who wish to become data engineers can do so, for the betterment of themselves, their employer, their country, and, ultimately, the world-for we share the belief that the most effective tool for world peace and stability is neither politics nor armaments, but rather the open and timely exchange of information. This book has been written with that goal in mind. Today numerous signs encourage us to expect broader information exchange in the years to come. The movement toward a true Integrated Services Digital Network (ISDN) is perhaps the clearest of these. Also, the development offormal protocol layers reflects both a great deal of brilliance and compromise and also the desire for a common language among data engineers."

Spis treści

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.