gpt-5-high· OpenAI
Arena Expert 5K
write matlab code to implement berlekamp massey algorithm for reed-solomon decoding…
- User
write matlab code to implement berlekamp massey algorithm for reed-solomon decoding using GF(2^8) and maximum 8 byte errors
- Assistant
Here’s a compact, self-contained MATLAB implementation of the Berlekamp–Massey algorithm for Reed–Solomon over GF(2^8) with up to 8 byte errors (t = 8). It takes 2t = 16 syndromes S0..S15 (first root at 0) and returns the error locator polynomial Λ(x), its degree L, and the error evaluator polynomial Ω(x) = [Λ(x)·S(x)] mod x^(2t).
function [Lambda, L, Omega] = bm_rs_gf256(S, t, prim) % bm_rs_gf256 Berlekamp–Massey for RS over GF(2^8) % [Lambda, L, Omega] = bm_rs_gf256(S, t, prim) % % Inputs: % S - 1x(2t) vector of syndromes S0..S(2t-1); numeric (0..255) or gf % t - error-correction capability (default 8) % prim - primitive polynomial (default 285, i.e., 0x11D) % % Outputs (gf arrays over GF(2^8), coeffs in ascending power of x): % Lambda - error locator polynomial Λ(x) = 1 + λ1 x + ... + λL x^L % L - degree of Λ(x) (number of errors if decoding succeeds) % Omega - error evaluator Ω(x) = [Λ(x)·S(x)] mod x^(2t), length 2t % % Notes: % - Field is GF(2^8) with primitive polynomial 'prim'. % - S should be computed as S_k = R(α^k), k=0..2t-1 (first root at 0). % - Addition/subtraction are the same (XOR) in GF(2^8). if nargin < 2 || isempty(t), t = 8; end if nargin < 3 || isempty(prim), prim = 285; end % Ensure GF(2^8) type and row vector if ~isa(S, 'gf') S = gf(uint16(S(:)).', 8, prim); else S = S(:).'; % force row % Ensure field matches 2^8 with given prim if S.m ~= 8 || S.prim_poly ~= prim S = gf(S.x, 8, prim); end end % If all syndromes are zero, no errors if all(S == 0) Lambda = gf(1, 8, prim); % Λ(x) = 1 L = 0; Omega = gf(zeros(1, 2*t), 8, prim); return; end % Initialize BM variables Lambda = gf(1, 8, prim); % C(x) B = gf(1, 8, prim); % B(x) L = 0; % current degree of C m_bm = 0; % index of last update b = gf(1, 8, prim); % last nonzero discrepancy % Main BM loop over n = 0..(2t-1) for n = 0:(numel(S)-1) % Compute discrepancy d = S_n + sum_{i=1..L} lambda_i * S_{n-i} d = S(n+1); for i = 1:L d = d + Lambda(i+1) * S(n+1-i); end if d == 0 % Just shift B: B(x) <- x * B(x) B = [gf(0, 8, prim), B]; else % Update C(x): C <- C + (d/b) * x^(n - m_bm) * B T = Lambda; coef = d / b; shift = n - m_bm; Lambda = gf_poly_add(Lambda, gf_poly_scale(gf_poly_shift(B, shift), coef)); % Degree update if needed if 2*L <= n L = n + 1 - L; B = T; b = d; m_bm = n; else % Otherwise continue shifting B B = [gf(0, 8, prim), B]; end end end % Trim Λ to degree L Lambda = Lambda(1:(L+1)); % Compute Ω(x) = [Λ(x) * S(x)] mod x^(2t) Omega_full = gf_poly_mul(Lambda, S); Omega = Omega_full(1:min(2*t, numel(Omega_full))); if numel(Omega) < 2*t Omega = [Omega, gf(zeros(1, 2*t - numel(Omega)), 8, prim)]; end end % ---------- Helper GF polynomial utilities (ascending powers) ---------- function C = gf_poly_add(A, B) % Add polynomials over GF(2^m) (ascending power). Length-align by zero pad. mexp = A.m; pp = A.prim_poly; la = numel(A); lb = numel(B); lc = max(la, lb); C = gf(zeros(1, lc), mexp, pp); C(1:la) = C(1:la) + A; C(1:lb) = C(1:lb) + B; end function C = gf_poly_mul(A, B) % Multiply polynomials over GF(2^m) (ascending power). mexp = A.m; pp = A.prim_poly; la = numel(A); lb = numel(B); C = gf(zeros(1, la+lb-1), mexp, pp); for i = 1:la if A(i) ~= 0 C(i:(i+lb-1)) = C(i:(i+lb-1)) + A(i) .* B; end end end function C = gf_poly_scale(A, s) % Scale polynomial by scalar s in GF. if s == 0 C = gf(zeros(size(A)), A.m, A.prim_poly); else C = A .* s; end end function C = gf_poly_shift(A, k) % Multiply polynomial by x^k (prepend k zeros). if k <= 0 C = A; else C = [gf(zeros(1, k), A.m, A.prim_poly), A]; end endUsage notes:
- Provide 16 syndromes S0..S15 as a row vector (numeric bytes or gf). For t = 8 and primitive polynomial 285 (0x11D), this matches RS(255,239) with first root at 0.
- The function returns Λ(x) (ascending coefficients), its degree L, and Ω(x) of length 16 suitable for Forney’s algorithm.
If you want, I can add a helper to compute the 16 syndromes from a received 255-byte word assuming first root at 0.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.