Electronics Guide

Random Processes and Ensembles

A random process X(t) can be viewed from two complementary perspectives:

• Ensemble view: At any fixed time t, X(t) is a random variable with a probability distribution describing the range of possible values across all realizations of the process
• Sample function view: For any specific realization, the process produces a deterministic time function called a sample function or realization

The complete statistical characterization of a random process requires specifying the joint probability distribution of X(t) at all possible combinations of time instants. In practice, lower-order statistics often suffice:

• First-order statistics: The mean function m(t) = E[X(t)] describes the expected value at each time instant
• Second-order statistics: The autocorrelation function R(t1, t2) = E[X(t1)X(t2)] characterizes how values at different times relate to each other
• Autocovariance: C(t1, t2) = E[(X(t1) - m(t1))(X(t2) - m(t2))] removes the mean to focus on fluctuations

For Gaussian processes, the first and second-order statistics provide a complete characterization since all higher-order statistics can be derived from them.

Stationarity and Ergodicity

Two properties dramatically simplify the analysis of random processes:

Stationarity: A process is strictly stationary if all its statistical properties are invariant to time shifts. For practical purposes, wide-sense stationarity (WSS) often suffices, requiring only:

• The mean m(t) = m is constant for all time
• The autocorrelation R(t1, t2) depends only on the time difference tau = t1 - t2, so R(t1, t2) = R(tau)

Wide-sense stationarity enables powerful analytical tools because the statistical properties become time-invariant, allowing frequency-domain analysis through the power spectral density.

Ergodicity: An ergodic process has the property that time averages computed from a single long realization equal ensemble averages across many realizations. This property is crucial for practical measurements because we typically have access to only one realization of a process. For ergodic processes:

Time average of X(t) = Ensemble average E[X(t)]

Most physical noise processes of interest are both stationary and ergodic, validating the common practice of estimating statistical parameters from single long measurements.

Power Spectral Density

For wide-sense stationary processes, the power spectral density S(f) describes how signal power is distributed across frequency. It relates to the autocorrelation function through the Wiener-Khinchin theorem:

S(f) = Fourier transform of R(tau)

Key properties of power spectral density include:

• Non-negative: S(f) is always greater than or equal to zero for all frequencies
• Real-valued: For real processes, S(f) is real and even symmetric
• Total power: Integrating S(f) over all frequencies yields the total signal power, which equals R(0)

Common spectral shapes encountered in practice include:

• White noise: S(f) = N0/2, constant for all frequencies; represents uncorrelated samples
• Pink (1/f) noise: S(f) proportional to 1/f; common in electronic devices and natural phenomena
• Bandlimited noise: S(f) is non-zero only within a specific frequency band
• Lorentzian: S(f) = K/(1 + (f/fc)^2); characteristic of first-order filtered white noise

Gaussian and Non-Gaussian Processes

Gaussian processes hold special importance in stochastic signal processing because of several favorable properties:

• Complete characterization: Mean and covariance fully specify all statistical properties
• Closure under linear operations: Any linear transformation of a Gaussian process produces another Gaussian process
• Central limit theorem: Many noise sources result from summing numerous small independent contributions, yielding approximately Gaussian statistics
• Mathematical tractability: Many optimal processing techniques have closed-form solutions for Gaussian signals

Non-Gaussian processes arise in various contexts including impulsive noise, clutter in radar, and communication signals with discrete symbol alphabets. Processing such signals often requires techniques beyond linear optimal filters, including nonlinear processing, robust estimation, and higher-order statistical analysis.

Wiener Filter Theory

The Wiener filter provides the optimal linear time-invariant filter for estimating a desired signal from observations corrupted by additive noise. Given an observed signal y(t) = s(t) + n(t), where s(t) is the signal of interest and n(t) is noise, the Wiener filter minimizes the mean-square error:

MSE = E[(s(t) - s_hat(t))^2]

where s_hat(t) is the filter output.

For the non-causal case (where the filter can use both past and future observations), the optimal frequency response is:

H(f) = S_ss(f) / (S_ss(f) + S_nn(f))

where S_ss(f) is the signal power spectrum and S_nn(f) is the noise power spectrum.

Key insights from this result:

• At frequencies where signal dominates noise, H(f) approaches 1 (pass the signal)
• At frequencies where noise dominates signal, H(f) approaches 0 (attenuate)
• The filter performs frequency-dependent weighting based on local SNR
• The result is optimal only for the specified signal and noise spectra

The causal Wiener filter, which can only use past and present observations, requires spectral factorization techniques and generally has a more complex frequency response.

Matched Filtering

When the task is to detect a known signal waveform in additive white Gaussian noise, the matched filter maximizes the output signal-to-noise ratio at the sampling instant. For a signal s(t) of duration T in white noise with spectral density N0/2:

h(t) = k x s(T - t)

The matched filter impulse response is a time-reversed and delayed version of the signal waveform. Key properties include:

• Maximum SNR: Output SNR = 2E/N0, where E is the signal energy
• Frequency response: H(f) = k x S*(f) x exp(-j2pi f T), the complex conjugate of the signal spectrum
• Correlation interpretation: Output at time T equals the correlation between input and signal template
• Optimality: No other linear filter achieves higher output SNR for white noise

Matched filters find extensive application in radar, sonar, and digital communications where known waveforms must be detected in noise. The concept extends to colored noise through prewhitening followed by matched filtering.

Linear Prediction

Linear prediction estimates future signal values based on a weighted sum of past values. For a discrete-time signal x[n], the p-th order linear predictor estimates:

x_hat[n] = sum(k=1 to p) of a[k] x x[n-k]

The optimal predictor coefficients minimize the mean-square prediction error and satisfy the Yule-Walker equations derived from the autocorrelation sequence. Linear prediction is fundamental to:

• Speech coding: Linear predictive coding (LPC) exploits the predictability of speech signals for compression
• Spectral analysis: Autoregressive modeling provides high-resolution spectral estimates
• Adaptive filtering: Prediction error drives coefficient adaptation in many algorithms
• Noise cancellation: Predictable components can be subtracted from measurements

The prediction error sequence has a white spectrum if the predictor order matches the signal's autoregressive structure, forming the basis for autoregressive spectral analysis.

Least Mean Square Algorithm

The LMS algorithm provides an adaptive implementation of Wiener filtering that adjusts filter coefficients in real-time to track changing signal statistics. The coefficient update rule is:

w[n+1] = w[n] + mu x e[n] x x[n]

where w is the coefficient vector, mu is the step size, e[n] is the error signal, and x[n] is the input vector.

Key characteristics of LMS include:

• Simplicity: Requires only multiplication and addition operations per sample
• Convergence: Converges in the mean to the Wiener solution for stationary inputs if the step size satisfies stability constraints
• Tracking: Can follow slowly time-varying optimal solutions
• Misadjustment: Steady-state excess MSE above Wiener optimum, proportional to step size

The step size parameter mu controls the tradeoff between convergence speed and steady-state error. Larger values give faster adaptation but higher misadjustment; smaller values give better steady-state performance but slower tracking.

Maximum Likelihood Estimation

Maximum likelihood (ML) estimation finds the parameter values that maximize the probability of observing the actual data. Given observations y and unknown parameters theta, the ML estimate is:

theta_ML = argmax L(theta; y)

where L(theta; y) = p(y|theta) is the likelihood function.

Properties of ML estimators include:

• Consistency: Converges to true parameter value as sample size increases
• Asymptotic efficiency: Achieves the Cramer-Rao lower bound asymptotically
• Asymptotic normality: Distribution approaches Gaussian for large sample sizes
• Invariance: ML estimate of a function of parameters is that function of the ML parameter estimates

For Gaussian observations, ML estimation often reduces to least-squares problems with closed-form solutions. In general, iterative numerical optimization may be required.

Bayesian Estimation

Bayesian estimation treats unknown quantities as random variables with prior distributions and updates beliefs based on observations. The posterior distribution is:

p(theta|y) = p(y|theta) x p(theta) / p(y)

Common point estimates derived from the posterior include:

• Maximum a posteriori (MAP): Mode of the posterior distribution; maximizes p(theta|y)
• Minimum mean-square error (MMSE): Mean of the posterior distribution; minimizes E[(theta - theta_hat)^2]
• Median: Minimizes mean absolute error

Bayesian estimation naturally incorporates prior knowledge and provides a complete probabilistic description of uncertainty through the posterior distribution. The choice of prior can significantly impact estimates, especially with limited data.

Cramer-Rao Lower Bound

The Cramer-Rao lower bound (CRLB) establishes the minimum achievable variance for any unbiased estimator. For a scalar parameter theta:

var(theta_hat) is greater than or equal to 1 / I(theta)

where I(theta) is the Fisher information:

I(theta) = E[(d/d(theta) ln p(y|theta))^2] = -E[d^2/d(theta)^2 ln p(y|theta)]

The CRLB provides several important insights:

• Performance benchmark: Establishes fundamental limits on estimation accuracy
• Efficiency measure: An estimator achieving the bound is called efficient
• SNR dependence: For many problems, CRLB scales inversely with SNR
• Sample size scaling: CRLB typically decreases inversely with number of samples

For vector parameters, the CRLB becomes a matrix inequality involving the Fisher information matrix.

Kalman Filtering

The Kalman filter provides optimal recursive estimation for linear dynamical systems with Gaussian noise. The system is described by:

• State equation: x[k+1] = A x[k] + B u[k] + w[k]
• Measurement equation: y[k] = C x[k] + v[k]

where w[k] and v[k] are zero-mean Gaussian noise with known covariances Q and R.

The Kalman filter recursively computes:

• Prediction: Propagates estimate forward using the state equation
• Update: Incorporates new measurement to refine the estimate
• Kalman gain: Optimally weights prediction versus measurement based on their relative uncertainties

Key properties include:

• Optimality: Provides minimum mean-square error estimate for linear Gaussian systems
• Recursiveness: Does not require storing all past measurements
• Covariance tracking: Automatically maintains estimate of uncertainty
• Extensions: Extended and unscented variants handle nonlinear systems approximately

The Kalman filter has become ubiquitous in navigation, tracking, control systems, and signal processing applications requiring state estimation from sequential measurements.

Periodogram and Averaging Methods

The periodogram, computed as the squared magnitude of the discrete Fourier transform, provides a direct but noisy spectral estimate. For N samples of x[n]:

P(f) = (1/N) |sum(n=0 to N-1) of x[n] exp(-j2pi fn)|^2

The periodogram is an inconsistent estimator: its variance does not decrease with increasing data length. Several techniques reduce variance:

• Bartlett method: Divides data into non-overlapping segments, computes periodograms of each, and averages the results
• Welch method: Uses overlapping segments with window functions to reduce variance while maintaining frequency resolution
• Blackman-Tukey method: Applies a window to the autocorrelation estimate before Fourier transformation

These methods trade off frequency resolution against variance reduction. More averaging reduces variance but requires either longer data records or accepting reduced frequency resolution.

Parametric Spectral Methods

Parametric methods assume the signal follows a specific model and estimate model parameters to determine the spectrum. The autoregressive (AR) model assumes:

x[n] = -sum(k=1 to p) of a[k] x[n-k] + e[n]

where e[n] is white noise. The power spectrum is then:

S(f) = sigma_e^2 / |1 + sum(k=1 to p) of a[k] exp(-j2pi fk)|^2

AR spectral estimation offers several advantages:

• High resolution: Can resolve closely spaced spectral peaks that nonparametric methods cannot
• Smooth spectra: Avoids the large variance of periodogram estimates
• Physical interpretation: AR models correspond to physical systems with resonances
• Short data: Can provide meaningful estimates from limited data

The model order p must be selected carefully: too low causes smoothing of spectral features; too high introduces spurious detail. Information criteria such as AIC and MDL provide principled order selection.

Subspace Methods

Subspace methods exploit the structure of signals composed of sinusoids in noise, decomposing the data covariance matrix into signal and noise subspaces. The MUSIC (Multiple Signal Classification) algorithm:

• Estimates the data covariance matrix from observations
• Performs eigendecomposition to identify signal and noise eigenvectors
• Computes a pseudo-spectrum from the noise subspace
• Identifies spectral peaks at frequencies where the steering vector is orthogonal to the noise subspace

MUSIC and related methods (ESPRIT, root-MUSIC) achieve super-resolution capability, resolving frequencies separated by less than the Rayleigh limit. However, they require:

• Accurate covariance matrix estimation
• Knowledge of the number of signal components
• Sufficient SNR for reliable subspace identification

These methods find application in direction-of-arrival estimation, frequency estimation, and system identification where high resolution from limited data is essential.

Time-Frequency Analysis

For non-stationary signals, time-frequency representations show how spectral content evolves over time. The short-time Fourier transform (STFT) applies windowed Fourier analysis:

STFT(t,f) = integral of x(tau) w(tau-t) exp(-j2pi f tau) d(tau)

The spectrogram, |STFT|^2, provides a time-frequency energy distribution subject to the uncertainty principle: high time resolution requires poor frequency resolution and vice versa.

Alternative time-frequency representations include:

• Wavelet transform: Uses scaled wavelets for multi-resolution analysis with better time resolution at high frequencies
• Wigner-Ville distribution: Quadratic representation with excellent resolution but cross-term artifacts for multi-component signals
• Cohen's class: Family of distributions with various tradeoffs between resolution and cross-term suppression

Time-frequency analysis is essential for analyzing signals with time-varying frequency content, such as speech, radar returns from moving targets, and biological signals.

Stochastic Number Representation

In unipolar stochastic representation, a value x in [0,1] is encoded as a random bit stream where each bit is independently 1 with probability x. For N bits, the expected count of 1s is Nx, and the actual count provides an estimate of x.

Bipolar representation extends the range to [-1,1] by encoding (x+1)/2 as the probability of 1. This maps x=-1 to all zeros, x=0 to equal probability, and x=1 to all ones.

Key characteristics of stochastic representation:

• Precision: Accuracy improves with stream length as 1/sqrt(N) due to statistical averaging
• Correlation sensitivity: Operations assume independent bit streams; correlation introduces errors
• Error tolerance: Bit flips cause small, graceful degradation rather than catastrophic errors
• Random number generation: Requires high-quality random or pseudo-random sources

The stochastic representation trades the compactness of binary for simplicity of operations, making it attractive for applications where approximate computation suffices.

Stochastic Arithmetic Operations

Arithmetic operations in stochastic computing require remarkably simple hardware:

Multiplication: A single AND gate multiplies two unipolar stochastic numbers. If bit stream A has probability pA of 1, and independent stream B has probability pB, then A AND B has probability pA x pB. For bipolar numbers, an XNOR gate computes the product.

Addition: A multiplexer with a stochastic select signal computes scaled addition. With select probability 0.5, the output represents (A + B)/2. Exact addition requires longer output streams or different encoding schemes.

Integration: A counter accumulates a stochastic bit stream, effectively computing the time integral of the encoded value.

Complex functions: Bernstein polynomials and other techniques enable implementation of arbitrary continuous functions using finite state machines operating on stochastic streams.

The hardware simplicity is striking: multiplication requires one gate, compared to hundreds or thousands of gates for binary multiplication. This advantage motivates stochastic computing for power-constrained and error-tolerant applications.

Decorrelation and Regeneration

Stochastic computation accuracy depends critically on the independence of input bit streams. When the same stochastic number is used multiple times, or when numbers share generation history, correlation errors accumulate.

Decorrelation techniques include:

• Independent random number generators: Use separate pseudo-random sequences for each stochastic number
• Isolation: Route different uses of the same value through independent decorrelating circuits
• Regeneration: Convert a bit stream back to probability and generate a fresh stream
• Deterministic approaches: Use low-discrepancy sequences or rotation rather than random sequences

The correlation problem represents one of the main challenges in practical stochastic computing systems, often negating the hardware simplicity advantages when extensive decorrelation is required.

Stochastic Computing Applications

Stochastic computing has found application in several domains:

• Neural networks: The inherent multiplication and accumulation operations map naturally to stochastic hardware, with noise providing implicit regularization
• Image processing: Edge detection, median filtering, and other operations tolerate the approximate nature of stochastic computation
• Decoding: LDPC and turbo code decoders benefit from stochastic implementation of belief propagation
• Control systems: Fuzzy logic and PID control have been demonstrated with stochastic circuits

The common thread is tolerance for approximation combined with requirements for low power, small area, or fault tolerance. Applications requiring high precision or deterministic timing are generally poor fits for stochastic computing.

Stochastic Resonance

Stochastic resonance is the counterintuitive phenomenon where adding noise to a nonlinear system can actually improve signal detection or information transmission. The classic example involves detecting a weak periodic signal by a threshold system:

• Without noise, a sub-threshold signal produces no output
• With optimal noise, the signal occasionally crosses threshold synchronously with the signal period
• Excessive noise overwhelms the signal

The signal-to-noise ratio at the output shows a peak at an optimal input noise level, rather than monotonically decreasing with added noise.

Applications of stochastic resonance include:

• Sensor systems: Enhancing detection of weak signals in threshold-based sensors
• Analog-to-digital conversion: Dithering improves effective resolution by randomizing quantization error
• Neural systems: Biological neurons may exploit stochastic resonance for signal detection
• Image processing: Adding noise before thresholding can reveal sub-threshold detail

Brownian Computing

Brownian computing exploits thermodynamic fluctuations to perform computation through random walks constrained by logical structure. Rather than fighting against thermal noise, Brownian computers harness it:

• Energy landscape: Computation state evolves through random transitions biased by an energy function encoding the desired computation
• Equilibrium distribution: The probability of finding the system in each state relates to the state's energy through the Boltzmann distribution
• Asymptotically zero energy: In principle, computation can occur with arbitrarily small energy dissipation by slowing the process

While practical Brownian computers face challenges from slow operation and the need for precise energy landscape control, they illuminate fundamental connections between thermodynamics and computation.

Probabilistic Computing

Probabilistic computing uses controlled randomness for algorithms that benefit from stochastic exploration of solution spaces:

• Monte Carlo methods: Estimate integrals and expectations through random sampling
• Simulated annealing: Finds global optima by accepting worse solutions with temperature-dependent probability
• MCMC sampling: Generates samples from complex probability distributions
• Randomized algorithms: Achieves efficiency or simplicity through randomization

Hardware implementations of probabilistic computing use physical noise sources (thermal noise, shot noise) or high-quality pseudo-random generators. The p-bit, a probabilistic analog of the deterministic bit, provides a building block for probabilistic computing hardware.

Neuromorphic Stochastic Systems

Biological neural networks operate in inherently noisy environments and may exploit randomness for computation. Neuromorphic systems emulating this behavior incorporate stochastic elements:

• Stochastic neurons: Neuron firing probability depends on membrane potential rather than having a deterministic threshold
• Synaptic noise: Random variation in synaptic weights provides implicit regularization
• Sampling-based inference: Neural networks can implement approximate Bayesian inference through stochastic dynamics
• Energy-based models: Restricted Boltzmann machines and deep belief networks use stochastic updates

These systems trade deterministic precision for energy efficiency, fault tolerance, and potentially more brain-like information processing capabilities.

Hypothesis Testing Framework

Binary hypothesis testing decides between two alternatives based on observation y:

• H0 (null hypothesis): Often representing noise-only or normal conditions
• H1 (alternative hypothesis): Signal present or abnormal condition

The decision rule partitions the observation space into regions favoring each hypothesis. Performance metrics include:

• Probability of detection (PD): Probability of correctly choosing H1 when H1 is true
• Probability of false alarm (PFA): Probability of incorrectly choosing H1 when H0 is true
• Probability of miss (PM): 1 - PD, incorrectly choosing H0 when H1 is true

The receiver operating characteristic (ROC) curve plots PD versus PFA as the decision threshold varies, characterizing the fundamental tradeoff between detection and false alarm rates.

Likelihood Ratio Test

The Neyman-Pearson lemma establishes that the likelihood ratio test is optimal: it maximizes PD for any given PFA constraint. The test computes:

L(y) = p(y|H1) / p(y|H0)

and compares L(y) to a threshold eta. The threshold is set to achieve the desired false alarm probability.

For Gaussian signals in Gaussian noise, the likelihood ratio test often simplifies to comparing a linear combination of observations to a threshold. This leads to practical detector implementations using matched filters followed by threshold comparison.

Extensions include:

• Composite hypotheses: When signal parameters are unknown, generalized likelihood ratio tests estimate parameters and then test
• Sequential detection: Sequential probability ratio tests minimize average sample number for given error probabilities
• M-ary detection: Generalizes to choosing among multiple hypotheses

Bayesian Decision Theory

Bayesian decision theory incorporates prior probabilities and costs to minimize expected loss. The risk (expected cost) for decision rule delta is:

R = sum over i,j of P(Hi) x P(decide Hj | Hi) x C(i,j)

where C(i,j) is the cost of deciding Hj when Hi is true, and P(Hi) is the prior probability of Hi.

The optimal Bayesian decision rule compares the likelihood ratio to a threshold determined by costs and priors:

eta = P(H0)/P(H1) x (C(0,1) - C(0,0))/(C(1,0) - C(1,1))

Special cases include:

• Minimum probability of error: Equal costs for all errors leads to maximum a posteriori (MAP) decision
• Minimax: Minimizes maximum risk when priors are unknown
• Neyman-Pearson: Constrains false alarm probability when costs are unknown

Detection in Colored Noise

When noise is not white, optimal detection requires accounting for noise correlation. The approach typically involves:

• Prewhitening: Filter the observation to whiten the noise, then apply white-noise optimal detection
• Colored noise matched filter: Modifies the matched filter frequency response by the inverse noise spectrum
• Generalized likelihood ratio: Includes noise covariance in the likelihood computation

For known signal in Gaussian noise with covariance matrix C, the optimal test statistic is:

T = s^T C^(-1) y

where s is the signal vector and y is the observation vector. This weighted inner product accounts for noise correlation in determining the optimal detection statistic.

Noise Source Generation

Quality random number generation is essential for stochastic computing and many signal processing applications. Analog noise sources include:

• Thermal noise: Amplified resistor noise provides a fundamental white noise source; requires sufficient amplification and bandwidth limiting
• Shot noise: Current fluctuations in reverse-biased diodes offer another fundamental source with white spectrum
• Avalanche noise: Zener diodes in breakdown provide high-amplitude noise but with non-Gaussian characteristics
• Chaotic circuits: Deterministic chaos provides pseudo-random sequences with good statistical properties

For stochastic computing applications, the noise source must be converted to digital bits through comparison with a threshold or reference level. The resulting bit stream's quality depends on the noise bandwidth, comparator speed, and threshold stability.

Continuous-Time Filter Implementation

Analog implementations of optimal filters offer advantages in power consumption and latency for appropriate applications. Key considerations include:

• Component accuracy: Filter response depends on RC or transconductance ratios; component variations affect frequency response
• Tuning: On-chip trimming or automatic tuning compensates for process variations
• Dynamic range: Noise floor and saturation limits constrain useful signal range
• Frequency scaling: Active filters can be designed for frequencies from sub-Hz to hundreds of MHz

Switched-capacitor techniques provide precise filter responses determined by capacitor ratios and clock frequency, combining analog signal processing with digital-like accuracy.

Stochastic Computing Hardware

Analog and mixed-signal implementations of stochastic computing include:

• Comparator-based conversion: Analog values become stochastic bit streams by comparing with random reference levels
• Analog accumulation: Integrate stochastic streams with switched-capacitor or current-mode circuits
• Hybrid architectures: Combine analog front-ends with digital stochastic processing
• Memristive implementations: Memristor arrays can implement stochastic matrix operations

The challenge is balancing the simplicity of stochastic operations against the overhead of random number generation and conversion between analog and stochastic representations.

Calibration and Adaptation

Practical stochastic signal processing systems require calibration to account for non-ideal behavior:

• Noise source characterization: Verify statistical properties and spectral content of random sources
• Offset compensation: Remove DC offsets that bias probability estimates
• Gain calibration: Ensure proper scaling between analog and stochastic domains
• Correlation measurement: Characterize any unintended correlation between supposedly independent streams

Adaptive techniques from estimation theory can continuously adjust system parameters to maintain performance despite drift and environmental changes.