Research project from a UROP at Imperial College London (Jun–Sep 2025).
Models classical error-decoding as a stochastic Bayesian inference problem and evaluates performance across noise distributions using Monte Carlo simulation.
Most classical decoders treat error correction as a deterministic algebraic problem. This project reframes it probabilistically: given a received codeword r, we want the posterior distribution over all possible transmitted codewords c:
A Markov-chain-inspired iterative sampler refines belief estimates over many steps, with importance weights derived directly from the noise model likelihood. This approach naturally handles any channel for which a likelihood function can be written - no Tanner graph or parity-check matrix required.
Each bit in the received word is a noisy observation. The decoder maintains a belief vector - a per-bit posterior probability - and updates it at every iteration by:
- Sampling candidate codewords from the current bit-probability prior.
- Weighting each candidate by its likelihood under the noise model (BSC, AWGN, or burst).
- Resampling (SIR step) to concentrate mass on high-likelihood regions.
- Updating the bit-probability vector as the weighted sample mean.
This is equivalent to running Sequential Importance Resampling (SIR) where the proposal distribution is factored over bits.
The iterative update forms a time-homogeneous Markov chain on the belief vector. Under mild conditions the chain converges to a fixed point near the MAP estimate. Convergence is tracked via the log-posterior of the best sample at each step.
| Model | Description | Parameter |
|---|---|---|
| BSC | Binary Symmetric Channel - each bit flips i.i.d. | Flip probability p |
| AWGN | Additive White Gaussian Noise with BPSK | Noise std σ |
| Burst | Two-state Markov chain (good/bad) | Burst entry probability |
.
├── src/
│ ├── decoder.py # Core: BayesianDecoder, noise channels, DecoderConfig
│ ├── run_simulation.py # BER sweep across noise parameter ranges
│ └── plot_results.py # Generates BER curve figures
├── tests/
│ └── test_decoder.py # pytest suite (channels + decoder correctness)
├── results/ # Saved .npz data and figures (git-ignored)
├── requirements.txt
└── README.md
git clone https://github.com/<your-username>/bayesian-error-decoding
cd bayesian-error-decoding
pip install -r requirements.txt
# Run the full Monte Carlo sweep (takes a few minutes)
python src/run_simulation.py
# Plot BER curves
python src/plot_results.py
# Run tests
pytest tests/ -vfrom src.decoder import DecoderConfig, BayesianDecoder, bsc_channel
import numpy as np
cfg = DecoderConfig(n_bits=16, n_samples=5000, n_iterations=40,
noise_model="bsc", noise_param=0.1)
rng = np.random.default_rng(42)
true_bits = rng.integers(0, 2, 16)
received = bsc_channel(true_bits, p=0.1, rng=rng)
decoder = BayesianDecoder(cfg)
result = decoder.decode(received)
print("True: ", true_bits)
print("Received:", received)
print("Decoded: ", result.decoded)
print(f"BER: {np.mean(result.decoded != true_bits):.3f}")BER curves are generated by sweeping the noise parameter for each channel model over 300 independent trials.
At low noise levels the Bayesian decoder approaches the performance of maximum-likelihood decoding; at high noise levels it degrades gracefully, reflecting the fundamental Shannon limit rather than hard failure.
Run python src/run_simulation.py && python src/plot_results.py to reproduce the figures in results/.
- No parity constraints: This decoder operates on raw codewords and does not exploit any code structure (e.g., LDPC parity checks). Adding a parity-constraint likelihood term would significantly improve performance.
- SIR degeneracy: At very high sample counts the importance weights can collapse. A local Metropolis-Hastings move after resampling would mitigate this.
- Scalability: The current implementation is O(N · n_samples) per decode step. For long codewords, a factored (per-bit) sampler or belief propagation would be more efficient.
This work was undertaken as part of a UROP (Undergraduate Research Opportunities Programme) at Imperial College London. The project sits at the intersection of coding theory and probabilistic inference, drawing on:
- Bayesian inference - posterior updating from noisy observations
- Monte Carlo methods - Sequential Importance Resampling (SIR / particle filtering)
- Markov chain theory - convergence analysis of the iterative belief update
MIT