|
|
Авторизация |
|
|
Поиск по указателям |
|
|
|
|
|
|
|
|
|
|
Ash R.B. — Information theory |
|
|
Предметный указатель |
space 250 257 262
-sequence 24
Abramson code 166
Algebra, of binary polynomials 147
Alphabet of a code 27
Alphabet of a source 172 185
Alphabet, of a channel 46 215
Ambiguous sequence 30
Arithmetic and geometric means, inequality of 25
Arzela — Ascoli theorem 270
Asymptotic equipartition property (AEP) 197 223
Band-limited functions 256 ff.
Bessel’s inequality 269
Binomial distribution 3 14 15
Binomial distribution, estimate of “tail” of 114
bits 11 84
Bose — Chaudhuri — Hocquenghem codes 156 ff.
Capacity of a binary symmetric channel 54
Capacity of a channel 1 3 50
Capacity of a discrete memoryless channel 50
Capacity of a finite state regular channel 220 228
Capacity of a general discrete channel 223
Capacity of a symmetric channel 53
Capacity of a time-continuous Gaussian channel 251 252
Capacity of a time-discrete Gaussian channel 234
Capacity of a time-discrete, amplitude-continuous channel 234
Capacity, calculation of 53 ff.
Capacity, X -capacity 224
Cascade combination, of discrete memoryless channels 85
Cayley — Hamilton theorem 139
Channel(s) 1
Channel(s), alphabet of 46 215
Channel(s), band-limited 256 ff.
Channel(s), binary erasure 86
Channel(s), binary symmetric 53 54 87
Channel(s), burst noise 213
Channel(s), capacity of see “Capacity”
Channel(s), cascade combination of 85
Channel(s), code for see “Code”
Channel(s), compound 228
Channel(s), connection of a source to 214 216
Channel(s), continuous 230 ff.
Channel(s), deterministic 51
Channel(s), discrete 47
Channel(s), discrete, memoryless 47
Channel(s), discrete, with finite memory 227
Channel(s), discrete, with memory 211 ff.
Channel(s), finite state 215 ff.
Channel(s), finite state, regular 216
Channel(s), information processed by 50 219
Channel(s), input n-sequence for 65
Channel(s), lossless 50
Channel(s), matrix of 49 212—215
Channel(s), matrix of, source-channel matrix 215—217
Channel(s), noiseless 27 51
Channel(s), output n-sequence for 65
Channel(s), product of 85
Channel(s), states of 46 215 230
Channel(s), sum of 85
Channel(s), symmetric 52
Channel(s), time-continuous Gaussian 251
Channel(s), time-discrete Gaussian 231
Channel(s), time-discrete Gaussian with average power limitation 231
Channel(s), time-discrete, amplitude-continuous 230
Channel(s), trap door 211
Channel(s), useless (zero-capacity) 52
Chebyshev’s inequality 15
Code 4
Code, (n, k) 99
Code, Abramson 166
Code, alphabet 27
Code, block 4 39 63
Code, Bose — Chaudhuri — Hocquenghem 156
Code, characters 27
Code, check digits of 93
Code, close-packed 132
Code, cyclic see “Cyclic code”
Code, error correcting 87 ff.
Code, Fire 167
Code, for a binary symmetric channel 87 ff.
Code, for a discrete memoryless channel 65 66
Code, for a finite state regular channel 220
Code, for a general discrete channel 223
Code, for a noiseless channel 27
Code, for a time-continuous Gaussian channel 251
Code, for a time-continuous Gaussian channel, explicit construction of 256
Code, for a time-discrete, amplitude continuous channel 230
Code, geometric interpretation of 90
Code, group 93 99
Code, group, coset of 100
Code, Huffman 42
Code, information digits of 93
Code, instantaneous see “Instantaneous code”
Code, lossless 132
Code, nonbinary 126
Code, optimal, absolutely 38
Code, optimal, absolutely, instantaneous 41
Code, parity check see “Parity check code”
Code, random 66 67 74 110
Code, single-error correcting 105
Code, single-error correcting, cyclic 161
Code, uniquely decipherable 28 29 35 40
Code, word 4 27 63 65
Coding theorem see “Fundamental theorem of information theory”
Communication entropy 24
Communication system 1
Conditional uncertainty 19 219 229 238 241
Convexity, of information and uncertainty 54 81 242
Convexity, of the logarithm 17
Corrector 94
Correlation detector 254
Coset leader ( = correctible error pattern) 103
Coset, of a group code 100
Coset, relation to correctible error patterns 102 103
Covariance function, of a random process 250 256 275
Critical rate, for the binary symmetric channel 117
Cycle set, of a binary matrix 136 143 144
Cycle set, of a feedback shift register 136
Cyclic code 137
Cyclic code, application to burst-error correction 164
Cyclic code, decoding of 161
Cyclic code, generation by a feedback shift register 137 151
Cyclic code, generator polynomial of 148
Cyclic code, properties of 147 ff.
Cyclic code, set of generators for 149
Cyclic code, single-error correcting 161
Decision scheme 1 4 60 65 220 230 251
Decision scheme, ideal observer see “Ideal observer decision scheme”
Decision scheme, maximum likelihood 62
Decision scheme, minimum distance see “Distance
Decision scheme, randomized 84
Decision scheme, with uniform error bound 62 66
Decoder see “Decision scheme”
Decoding sets 65
Dini’s theorem 274
Distance (between code words) 87 ff. 126
Distance (between code words), minimum distance decoder 88 126 254
Distance (between code words), minimum distance decoder, for a parity check code 95
Distance (between code words), minimum distance principle 87 88
Distance (between code words), minimum, bounds on 129
Distance (between code words), relation to error correction 89
Effective procedure, for determining existence of steady state probabilities in a finite Markov chain 180 218
Effective procedure, for determining whether a finite state channel is regular 218
Eigenvalues, eigenfunctions, and eigenvectors 210 250 264
Encoder 1 4
entropy 24
Ergodic information source see “Source”
Error bounds (exponential) 77 ff. 227 260
Error bounds (exponential), for general binary codes 113 ff.
Error bounds (exponential), for nonbinary codes 127
| Error patterns 95
Error patterns, correctible, relation to cosets 102 103
Fano’s inequality 80 243
Feedback shift register 134 ff.
Feedback shift register, characteristic matrix of 135
Feedback shift register, cycle set of 136
Feedback shift register, generation of a cyclic code by 137 151
Feedback shift register, state (content) of 135
Field 126 142
Field, Galois (finite) 142
Fire code 167
Fourier transforms 251 257 258 281
Fourier transforms, convolution 282
Fourier transforms, Parseval relation 258 282
Fundamental lemma (in the proof of the fundamental theorem) 68 86 232
Fundamental theorem of information theory 1
Fundamental theorem of information theory, for the discrete memoryless channel 66 307
Fundamental theorem of information theory, for the discrete memoryless channel, algorithmic proof 68
Fundamental theorem of information theory, for the discrete memoryless channel, random coding proof 74
Fundamental theorem of information theory, for the discrete memoryless channel, Shannon’s original proof 66
Fundamental theorem of information theory, for the finite state regular channel 222
Fundamental theorem of information theory, for the general discrete channel 223
Fundamental theorem of information theory, for the time-continuous Gaussian channel 252
Fundamental theorem of information theory, for the time-discrete Gaussian channel 234
Fundamental theorem of information theory, strong converse to see “Strong converse”
Fundamental theorem of information theory, weak converse to see “Weak converse”
Generator matrix, of a cyclic code 149
Generator matrix, of a parity check code 132
Generator polynomial (of a cyclic code) 148
Generator polynomial (of a cyclic code), relation to the minimal polynomial of a matrix 150
Generators, set of, for a cyclic code 149
Generators, set of, for a parity check code 110
Greatest common divisor, of two polynomials 141
Group 96
Group code 93 99
Group code, coset of 100
Group, abelian (commutative) 96 141 147
Grouping axiom, for the uncertainty function 8 80 81
Grouping axiom, generalized 26
Hamming bound, for general binary codes 90 133
Hamming bound, for parity check codes 107
Hamming bound, strengthened 127
Hamming code 130 133
Hamming distance see “Distance”
Hilbert space 250 262
Hilbert space, Bessel’s inequality 269
Hilbert space, inner product 262
Hilbert space, norm 262
Hilbert space, orthogonal complement of a subspace 268
Hilbert space, orthonormal family 266
Hilbert space, parallelogram law 265
Hilbert space, space spanned by a subset 267
Huffman code 42
Ideal observer decision scheme 61 73
Ideal observer decision scheme, for the binary symmetric channel 88
Ideal observer decision scheme, for the q-ary symmetric channel 126
Ideal observer decision scheme, for the time-discrete Gaussian channel 254
Ideal, in the algebra of binary polynomials 149
Independent random variables 14 39 195
Independent random variables, as a Markov information source 185
Independent random variables, uncertainty of 18 19 21 239 241 242
information 4
Information, convexity of 54 242
Information, conveyed about one random variable by another 22 23 239 242
Information, conveyed about one stationary sequence of random variables by another 219
Information, processed by a channel 50 219
Information, source of see “Source”
Instantaneous code 28 39
Instantaneous code, conditions for existence of 33
Instantaneous code, optimal 41
Instantaneous code, relation to sequence of “yes or no” questions 40
Integral operator 269 ff.
Integral operator, associated with a covariance function 250 282
Integration, of second order random processes 275 ff.
Irreducible polynomial 140 146
Joint uncertainty 18—21 238—240
Karhunen — Loeve theorem 250 277
Karhunen — Loeve theorem for Brownian motion 279
Karhunen — Loeve theorem for Gaussian processes 279
Language, uncertainty of 206
Linear operator (on a Hilbert space) 262 ff.
Linear operator (on a Hilbert space), bilinear form of 265
Linear operator (on a Hilbert space), compact (completely continuous) 263
Linear operator (on a Hilbert space), continuous (bounded) 262
Linear operator (on a Hilbert space), integral operator 269 ff.
Linear operator (on a Hilbert space), integral operator, associated with a covariance function 250 282
Linear operator (on a Hilbert space), quadratic form of 265
Linear operator (on a Hilbert space), symmetric (self-adjoint) 265
Markov chain(s) (finite) 171
Markov chain(s) (finite), essential sets of 180 183
Markov chain(s) (finite), indecomposable 181 184
Markov chain(s) (finite), periodic and aperiodic states of 183 184
Markov chain(s) (finite), regular 185
Markov chain(s) (finite), states of 171
Markov chain(s) (finite), stationary distribution of 174 181 184
Markov chain(s) (finite), steady state probabilities of 174 176
Markov chain(s) (finite), steady state probabilities of, effective determination of existence of 180 218
Markov chain(s) (finite), theory of 172 ff.
Markov chain(s) (finite), transient states of 180 183
Markov chain(s) (finite), transition matrix (Markov matrix, stochastic matrix) of 171
Markov information source see “Source”
Markov property 171
Matrix 138 ff.
Matrix, binary 138
Matrix, binary, characteristic polynomial of 138
Matrix, binary, cycle set of 136 143 144
Matrix, binary, minimal polynomial of see “Minimal polynomial”
Matrix, binary, period of 143
Matrix, binary, polynomial in 140
Matrix, binary, powers of, and matric polynomials 145
Matrix, binary, with maximal period 144
Matrix, channel 49 212—215
Matrix, connection, of a unifilar Markov source 209
Matrix, doubly stochastic 26
Matrix, Markov (stochastic, transition) 171
Matrix, parity check 93 106
Matrix, source-channel 215—217
Maximal period 144
Maximum likelihood decision scheme 62
Mercer’s theorem 272
Message 1 27 63
Minimal polynomial of a matrix 139
Minimal polynomial of a matrix, irreducible 140 141 143 144
Minimal polynomial of a matrix, relation to generator polynomial of a cyclic code 150
Minimum distance decoder see “Distance”
Noise 1
Noiseless coding 27 ff.
Noiseless coding, theorem 13 37
Nonnegative definite function 272
Order of a unifilar Markov source 189 ff.
Parity check code(s) 91 ff. 126
Parity check code(s), adequacy of 110 ff.
Parity check code(s), bounds on error-correcting ability of 105 ff.
Parity check code(s), generator matrix of 132
Parity check code(s), set of generators for 110
Parity check matrix 93 106
Period of a matrix 143
Period of a matrix, maximal 144
Polynomial(s), algebra of 147
Polynomial(s), characteristic 138
Polynomial(s), generator see “Generator polynomial”
Polynomial(s), in a binary matrix 140
Polynomial(s), irreducible 140 146
Polynomial(s), minimal see “Minimal polynomial”
Polynomial(s), representation of, by a binary sequence 147
Prefix 28
Probability of error 65
Probability of error, average 65 73
Probability of error, exponential bounds on see “Error bounds”
Probability of error, for a group code 104
|
|
|
Реклама |
|
|
|