GLOBAL KNOWLEDGE ARK

Reference library

Foundations

Explore concepts, laws, equations and methods, with clear explanations of their use and sources. Choose an area of study or find a specific entry.

More filters

Reference entries

Showing 151–180 of 1709 reference entries

Mathematics & logicTotal derivative in finite dimensions

Differentiability means a linear approximation with smaller-order error.

DefinitionMathematics & logicDouble integrals on simple regions

A continuous double integral can be evaluated by slicing.

Mathematical statementMathematics & logicGradient, divergence and curl

These coordinate derivatives have different input and output types.

DefinitionMathematics & logicStokes' circulation theorem

Circulation around a boundary equals oriented curl flux.

Mathematical statementMathematics & logicDivergence theorem

Outward boundary flux equals integrated divergence.

Mathematical statementMathematics & logicLocal existence and uniqueness for autonomous ODEs

Local Lipschitz continuity ensures one local trajectory.

Mathematical statementMathematics & logicConstant-coefficient linear ODE systems

The matrix exponential solves a finite linear system.

Mathematical statementMathematics & logicLaplace, heat and wave equation problems

A PDE becomes a solution problem only with a domain and data.

ModelMathematics & logicRandom variables and probability distributions

A distribution assigns probabilities to a random variable's values.

DefinitionMathematics & logicNormal distribution

A normal model is specified by location and positive scale.

DefinitionMathematics & logicBinomial and Poisson count models

Different count mechanisms require different distributions.

DefinitionMathematics & logicWeak law of large numbers

A sample mean concentrates near its mean under stated assumptions.

Mathematical statementMathematics & logicClassical iid central limit theorem

Centered sample averages have an asymptotic normal law.

Mathematical statementMathematics & logicConditional masses and densities

A conditional distribution renormalizes a joint law.

DefinitionMathematics & logicLikelihood and Bayesian updating

Likelihood is a function of a parameter given observed data.

MethodMathematics & logicNull tests, significance and p-values

A p-value is calibrated under a specified null model.

MethodMathematics & logicSampling, randomization and confounding

Selection and treatment assignment answer different questions.

MethodMathematics & logicPermutation inference under exchangeability

Distribution-free procedures still require assumptions.

MethodInformationFinite-alphabet mutual information

Mutual information measures statistical dependence in bits.

DefinitionInformationNear-lossless source coding threshold

Entropy bounds asymptotic compression for an iid source.

Mathematical statementInformationDiscrete memoryless channel capacity

Capacity is the maximal asymptotically reliable rate.

Mathematical statementInformationHamming distance and error correction

Separated codewords permit bounded symbol-error recovery.

Mathematical statementInformationInternet protocol layers

Protocol layers divide communication responsibilities.

DefinitionInformationTCP reliable byte-stream transport

TCP orders bytes and retransmits detected losses.

MethodInformationEncryption, hashes and message authentication

Cryptographic primitives serve distinct security properties.

DefinitionInformationPublic-key digital signatures

A signing key and a verification key have different roles.

DefinitionInformationComputable reductions and undecidability

Reduction direction determines which impossibility transfers.

Mathematical statementInformationDecision classes P and NP

Polynomial solving and polynomial verification differ.

DefinitionInformationNP-hardness and NP-completeness

NP-completeness combines verification and reduction hardness.

DefinitionInformationBounded-error randomized computation

Random choices permit a stated probability of error.

Definition
Mathematical statementSource checked

Near-lossless source coding threshold

Information

Entropy bounds asymptotic compression for an iid source.

Key knowledge

For an iid finite-alphabet source, fixed-length block schemes at rates above H(X) bits per symbol can have block error tending to zero. At a fixed rate below H(X), block error tends to one.

Conditions and scope

  • The alphabet distribution is fixed, logarithms are base two, and block length grows.
  • This is near-lossless asymptotic coding, not exact reconstruction for every finite block.
Sources · 1

References

Sources retain their recorded scope. A source link alone does not establish verification of every statement.

  1. EE276 2024, Lecture 4Tsachy Weissman / Stanford UniversityCourse notes · PDFweb.stanford.eduRead source

Evidence and review

Section 2.2, direct/converse theorems for iid finite-alphabet near-lossless fixed-length block coding.

2026-10-10 · Lecture 4 section 2.2 source-coding direct and converse statements.

Related reference entries

Explore relationships within this area of study and its connections to other areas.

Showing 1–5 of 5 relationships

Scientific relationships · 5 / 5

The relationship type describes the connection. Its linked statements, sources and conditions define the scope.

  1. Uses definition
    Relationship sources · 1

    Linked statements

    • For an iid finite-alphabet source, fixed-length block schemes at rates above H(X) bits per symbol can have block error tending to zero. At a fixed rate below H(X), block error tends to one.
  2. Uses definition
    Relationship sources · 1

    Linked statements

    • A binary prefix code has no whole codeword as another's initial segment, permitting immediate sequential decoding. Uniquely decodable code lengths satisfy Σ2⁻ˡⁱ≤1; conversely positive integer lengths satisfying the inequality admit a prefix code. Expected length is at least source entropy.
  3. Uses definition
    Relationship sources · 1

    Linked statements

    • For iid finite-alphabet X₁,…,Xₙ, −n⁻¹log₂p(X₁,…,Xₙ) converges in probability to H(X₁). With high probability the sequence lies in a typical set of about 2ⁿᴴ probability-scale possibilities, which supports near-lossless block compression.
  4. Related to
    Relationship sources · 1

    Linked statements

    • For independent repetitions of a finite-alphabet joint law p(x,y), an encoder observing X and a decoder possessing Y can recover X with vanishing block error at rates above H(X|Y); rates below it are impossible. Random binning exploits correlation without revealing Y to the encoder. This is a Slepian–Wolf special case; separate encoders, lossy reconstruction, nonstationary sources or unavailable side information require their own regions.

    Distributed side information changes the coding setting.

  5. Related to
    Relationship sources · 2

    Linked statements

    • For an iid source with law p(x) and specified distortion d(x,x-hat), R(D) minimizes mutual information over reconstruction laws meeting expected distortion D. For a zero-mean Gaussian source of variance sigma² and squared-error distortion, R(D)=one-half log2(sigma²/D) for 0<D<sigma² and zero for D≥sigma². Changing distortion, side information or source memory changes the answer.

    Lossy coding uses a specified distortion budget.

Entry detailsPermanent link to this entry ↗
Record identity
info-source-coding
Revision
university-reference.1
Structured reference record
University reference