Исследование обнаружения ошибок с помощью CRC
В этом примере исследуется, как циклический избыточный код (CRC, Cyclic Redundancy Check) обнаруживает ошибки при передаче пакетов по зашумлённому двоичному каналу. Модель Engee передаёт случайные пакеты, добавляет к ним проверочные биты CRC, искажает их в двоичном симметричном канале, проверяет синдром на приёме и считает верные, обнаруженные и необнаруженные ошибочные пакеты. Модель собрана из библиотечных блоков Engee, в том числе General CRC Generator и General CRC Syndrome Detector. Скрипт управляет моделью программно и сравнивает результаты моделирования с точной теорией, рассчитанной по весовому спектру кода. Опыты можно ставить и в веб-приложении на Genie Framework, которое запускает ту же модель. Пример полезен инженерам и студентам, изучающим помехоустойчивое кодирование и статистическое моделирование каналов связи.
В любом канале связи часть битов искажается помехами. Чтобы приёмник узнал об ошибке, передатчик добавляет к данным избыточные проверочные биты. CRC — один из самых распространённых способов такой проверки: его используют в Ethernet, USB, протоколах промышленных сетей, в файловых архивах и при хранении данных.
CRC только обнаруживает ошибки, но не исправляет их. Пакет с ошибкой приёмник отбрасывает или запрашивает повторно. Поэтому главный показатель качества CRC — вероятность того, что ошибка пройдёт незамеченной.
В этом примере мы:
- Кратко разберём теорию CRC и выведем точные вероятности трёх исходов приёма пакета.
- Изучим модель и проверим её на опытах с заранее известным ответом.
- Сравним результаты моделирования с теорией в широком диапазоне вероятности ошибки.
- Запустим веб-приложение, в котором опыты можно ставить без программирования.
Теория CRC
Биты пакета рассматриваются как коэффициенты многочлена над полем GF(2), где сложение — это исключающее ИЛИ. Информационные биты образуют многочлен степени меньше . Образующий полином степени задаётся списком степеней: [5, 3, 0] означает .
Кодер CRC приписывает к данным остаток от деления:
Полная длина пакета , при исходных настройках , , . Любое кодовое слово делится на без остатка.
Приёмник вычисляет синдром — остаток от деления принятого слова на . Если канал добавил вектор ошибок , синдром равен . Ошибка не обнаруживается, только если сам является ненулевым кодовым словом.
Двоичный симметричный канал независимо инвертирует каждый бит с вероятностью . Каждый пакет попадает ровно в один из трёх классов:
где — число кодовых слов веса (весовой спектр кода). При все векторов ошибок равновероятны, и доля необнаруженных ошибок равна : из векторов с нулевым синдромом нужно исключить единственный случай без ошибок. Для и это почти .
Описание модели
.png)
Модель crc_error_detection.engee собрана только из библиотечных блоков Engee и работает с фиксированным шагом . Один шаг — один пакет, поэтому время моделирования означает номер пакета, а не физическое время.
| Узел | Блоки Engee | Назначение |
|---|---|---|
| Источник данных | Bernoulli Binary Generator Payload |
случайных информационных бит на каждом шаге |
| Кодер | General CRC Generator CRC Encoder |
добавляет проверочных бит |
| Канал | Bernoulli Binary Generator Channel Noise, Logical Operator XOR Binary Symmetric Channel |
вектор ошибок с вероятностью единицы складывается с кодовым словом по XOR |
| Детектор | Data Type Conversion To Double, General CRC Syndrome Detector CRC Detector |
выделяет информационные биты и признак ненулевого синдрома |
| Обработка ошибок | Logical Operator (XOR, OR, NOT, AND, NOR), Sum of Elements, Mux, Data Type Conversion | формирует вектор событий пакета |
| Счётчики | Add Packet Statistics и Unit Delay Previous Totals |
накапливают события |
| Остановка | Constant, Relational Operator, Logical Operator OR, Stop Simulation | останавливают модель по пределам |
Узел обработки ошибок формирует на каждом шаге вектор событий пакета:
где — признак ненулевого синдрома, — признак того, что изменился хотя бы один информационный бит. Элементы вектора означают: передан пакет, ошибка обнаружена, ошибка пропущена, пакет верен, число инвертированных бит. Сумматор Packet Statistics вместе с блоком задержки Previous Totals накапливает вектор событий в пять счётчиков.
Обратите внимание на класс «пакет верен»: он требует, чтобы не изменились информационные биты и синдром был нулевым. Ошибка только в проверочных битах даёт ненулевой синдром и засчитывается как обнаруженная — приёмник не может отличить её от ошибки в данных.
Параметры блоков — переменные рабочей области crc_n, crc_k, crc_p, crc_seed, crc_packet_limit и crc_error_limit. Их задаёт код скрипта перед каждым запуском. Модель можно воспроизводимо пересоздать скриптом resources/julia/build_model.jl.
Параметры блоков
Подключим функции управления моделью из resources/julia/crc_runtime.jl и справочник полиномов, откроем модель и выведем основные параметры ключевых блоков командой engee.get_param. Все пути строятся от папки скрипта через @__DIR__.
using JSON3, Printf, Plots
gr()
resources_dir = joinpath(@__DIR__, "resources")
include(joinpath(resources_dir, "julia", "crc_runtime.jl"))
include(joinpath(resources_dir, "julia", "polynomials.jl"))
crc_open_model()
show_params = Dict(
"Payload" => ["SamplesPerFrame", "ProbabilityOfZero", "InitialSeed", "SampleTime"],
"CRC Encoder" => ["GeneratorPolynomial", "InitialStates", "DirectMethod", "ReflectInputBytes", "FinalXOR"],
"Channel Noise" => ["SamplesPerFrame", "ProbabilityOfZero", "InitialSeed", "SampleTime"],
"Binary Symmetric Channel" => ["Operator"],
"CRC Detector" => ["GeneratorPolynomial", "InitialStates", "DirectMethod"],
"Data Changed" => ["Operator"], "Any Bit Changed" => ["Operator", "Inputs"],
"Undetected" => ["Operator"], "Correct" => ["Operator"],
"Previous Totals" => ["InitialCondition", "SampleTime"],
"Stop Limits" => ["Value"], "Limit Reached" => ["Operator"])
for b in ["Payload", "CRC Encoder", "Channel Noise", "Binary Symmetric Channel", "CRC Detector", "Data Changed",
"Any Bit Changed", "Undetected", "Correct", "Previous Totals", "Stop Limits", "Limit Reached"]
prm = engee.get_param("crc_error_detection/" * b)
println(rpad(b, 26), prm["BlockPath"])
println(" "^26, join(["$k = $(prm[k])" for k in show_params[b]], "; "))
end
Параметры задаются переменными рабочей области. Шаг источников равен и на один бит, поэтому за шаг модели каждый источник выдаёт кадр из или бит. Параметры CRC соответствуют классической схеме: нулевое начальное состояние, без прямого метода, отражения бит и итогового XOR. Порог остановки по второму, четвёртому и пятому счётчикам равен , то есть они на остановку не влияют.
Справочник полиномов
Файл polynomials.jl содержит таблицу образующих полиномов циклических кодов Боуза — Чоудхури — Хоквингема (БЧХ). Для каждой строки вычислены список степеней в формате модели и признак supported: поддерживают ли полином блоки CRC Engee. Выведем таблицу.
println(rpad("n", 5), rpad("k", 5), rpad("t", 5), rpad("блоки Engee", 13), "полином (степени)")
for x in crc_presets
println(rpad(x.n, 5), rpad(x.k, 5), rpad(x.t, 5), rpad(x.supported ? "да" : "нет", 13), x.poly)
end
@printf("Поддерживается %d из %d полиномов\n", count(x -> x.supported, crc_presets), length(crc_presets))
Столбец — число ошибок, которое исправлял бы соответствующий код БЧХ. Модель только обнаруживает ошибки, поэтому приведено как справка. Доступны все коды длины , и и пять кодов длины . Шесть кодов длины с полиномами степени от до библиотечные блоки CRC не поддерживают: их степень больше .
Проверка модели
Файл crc_runtime.jl содержит шесть функций:
crc_validateпроверяет параметры опыта: длину блока, вероятность, список степеней полинома, пределы и seed;crc_poly_literalзаписывает вектор степеней полинома в виде литерала для блоков CRC;crc_open_modelзагружает модель, если она ещё не открыта;crc_signalнаходит записанный сигнал блока в результатах моделирования;crc_run_jsonпринимает параметры в виде строки JSON, записывает их в переменные рабочей области и в параметры блоков CRC, запускает модель командойengee.runи возвращает итоговые счётчики в виде JSON;crc_reference_encode— независимый кодер CRC: деление многочленов «в столбик» для проверки блока General CRC Generator.
Формат JSON выбран потому, что той же функцией пользуется веб-приложение. Запустим контрольный опыт: , , полином [5, 3, 0], пакетов.
crc_example_config = Dict("n" => 19, "p" => 0.1, "poly" => [5, 3, 0],
"blocksToStop" => 2000, "errorsToStop" => 2000, "seed" => 12345)
crc_example_result = JSON3.read(crc_run_json(JSON3.write(crc_example_config)))
@printf("Всего %d: верно %d, обнаружено %d, не обнаружено %d; битовых ошибок %d; %s; %.1f с\n",
crc_example_result.packets, crc_example_result.correct, crc_example_result.detected,
crc_example_result.undetected, crc_example_result.bit_errors, crc_example_result.stop_reason,
crc_example_result.seconds)
@assert crc_example_result.correct + crc_example_result.detected + crc_example_result.undetected == crc_example_result.packets
За пакетов при верно принято пакетов, ошибочных пакетов обнаружено и пропущено. Это количество пакетов, а не бит: в канале было инвертировано бит из , то есть при ожидаемых . Доля верных пакетов совпадает с теоретической . Сумма трёх классов равна числу переданных пакетов, эту проверку выполняет @assert.
Теперь выполним набор контрольных опытов. Файл verify_model.jl запускает модель в шести опытах с заранее известным ответом и проверяет, что недопустимые параметры отклоняются. Среди проверок — сравнение выхода блока General CRC Generator с независимым кодером crc_reference_encode на реальных пакетах модели и проверка того, что любая одиночная ошибка даёт ненулевой синдром. Результат записывается в resources/data/verification.json.
verification = JSON3.read(include(joinpath(resources_dir, "julia", "verify_model.jl")))
println("Все проверки пройдены: ", verification.passed)
for t in verification.tests
if haskey(t, :result)
r = t.result
@printf(" %-48s n=%-3d p=%-4g пакетов %-5d верно %-5d обн. %-5d не обн. %d\n",
t.case, r.n, r.p, r.packets, r.correct, r.detected, r.undetected)
else
@printf(" %-48s кадров %d, одиночных ошибок %d\n", t.case, t.frames, t.single_bit_cases)
end
end
Все проверки пройдены:
- без шума все пакетов приняты верно;
- для кода инверсия всех бит превращает кодовое слово в другое кодовое слово: слово из семи единиц делится на . CRC такую ошибку не видит, и блок Stop Simulation останавливает модель ровно после необнаруженных ошибок;
- для длины такая же инверсия всегда обнаруживается;
- одинаковый seed воспроизводит все счётчики;
- выход блока General CRC Generator совпал с независимым кодером на всех пакетах, и все одиночных ошибок дают ненулевой синдром. Значит, библиотечный блок вычисляет CRC именно по формуле из теоретической части;
- полином наибольшей поддерживаемой степени из таблицы работает без ошибок, а полином степени отклоняется до запуска модели.
Сравнение с теорией
Рассчитаем точный весовой спектр кода с полиномом . Для этого закодируем эталонным кодером все информационных слова и подсчитаем веса кодовых слов. Функция theory по спектру вычисляет вероятности трёх классов пакетов.
poly = [5, 3, 0]; n_c, k_c = 19, 14
A = zeros(Int, n_c + 1) # A[w+1] — число кодовых слов веса w
for m in 0:2^k_c-1
payload = [(m >> (k_c - i)) & 1 for i in 1:k_c]
A[count(==(1), crc_reference_encode(payload, poly))+1] += 1
end
println("Весовой спектр A_w (w: число слов): ", join(["$(w):$(A[w+1])" for w in 0:n_c if A[w+1] > 0], " "))
@printf("Минимальный ненулевой вес d_min = %d\n", findfirst(>(0), A[2:end]))
theory(p) = begin
pc = (1 - p)^n_c
pu = sum(A[w+1] * p^w * (1 - p)^(n_c - w) for w in 1:n_c)
(correct = pc, undetected = pu, detected = 1 - pc - pu)
end
Минимальный вес ненулевого кодового слова , поэтому CRC гарантированно обнаруживает любые одиночные и двойные ошибки. Слов нечётного веса много: полином не содержит множителя , поэтому, в отличие от многих стандартных CRC, например CRC-16, он не обнаруживает все ошибки нечётной кратности. Любой пакет ошибок длиной до бит обнаруживается: такой вектор ошибок не делится на .
Запустим модель для вероятностей инверсии бита от до , по пакетов в каждой точке, и сравним доли трёх классов пакетов с теорией.
ps = [0.001, 0.003, 0.01, 0.03, 0.1, 0.2, 0.3, 0.5]
sim = Dict{Float64, Any}()
for p in ps
cfg = Dict("n" => 19, "p" => p, "poly" => poly, "blocksToStop" => 20000, "errorsToStop" => 1_000_000, "seed" => 777)
sim[p] = JSON3.read(crc_run_json(JSON3.write(cfg)))
th = theory(p); r = sim[p]
@printf("p = %-5g верно %.4f (теор. %.4f) обн. %.4f (%.4f) не обн. %.2e (%.2e)\n", p,
r.correct / r.packets, th.correct, r.detected / r.packets, th.detected,
r.undetected / r.packets, th.undetected)
end
Доли верных и обнаруженных пакетов совпадают с теорией до второго-третьего знака во всём диапазоне. Необнаруженные ошибки — редкое событие, и при малых модель не зарегистрировала ни одного. Чтобы понять, согласуется ли это с теорией, нужна оценка статистической погрешности.
Построим две панели: доли верных и обнаруженных пакетов на обычной шкале, затем долю необнаруженных ошибок на логарифмической шкале. Для каждой ненулевой оценки покажем 95-процентный доверительный интервал Уилсона. Для доли его границы
Если модель не зарегистрировала событие, вместо невидимого на логарифмической шкале нуля покажем треугольником верхнюю 95-процентную границу вероятности. Такой треугольник не является измеренной долей. Горизонтальную линию не рисуем: значение относится только к , а не ко всему диапазону .
# Теоретические вероятности считаются из точного весового спектра A_w.
pgrid = 10 .^ range(-3, log10(0.5); length = 200)
function wilson95(k, n)
z = 1.959963984540054
q = k / n
den = 1 + z^2 / n
mid = (q + z^2 / (2n)) / den
half = z * sqrt(q * (1 - q) / n + z^2 / (4n^2)) / den
(max(0.0, mid - half), min(1.0, mid + half))
end
main_plot = plot(pgrid, [theory(p).correct for p in pgrid];
color = :seagreen, lw = 2, label = "верно, теория", xscale = :log10,
ylims = (-0.03, 1.05), ylabel = "Доля пакетов",
title = "CRC x^5+x^3+1, n = 19: модель и точная теория",
legend = :outertopright, left_margin = 5Plots.mm)
plot!(main_plot, pgrid, [theory(p).detected for p in pgrid];
color = :royalblue, lw = 2, label = "обнаружено, теория")
scatter!(main_plot, ps, [sim[p].correct / sim[p].packets for p in ps];
color = :seagreen, marker = :circle, ms = 6, label = "верно, модель")
scatter!(main_plot, ps, [sim[p].detected / sim[p].packets for p in ps];
color = :royalblue, marker = :square, ms = 6, label = "обнаружено, модель")
rare_plot = plot(pgrid, [theory(p).undetected for p in pgrid];
color = :orangered, lw = 2, label = "не обнаружено, теория",
xscale = :log10, yscale = :log10, ylims = (1e-8, 0.1),
xlabel = "Вероятность инверсии бита p", ylabel = "Доля пакетов",
legend = :outertopright, left_margin = 5Plots.mm)
nonzero_ps = [p for p in ps if sim[p].undetected > 0]
zero_ps = [p for p in ps if sim[p].undetected == 0]
for (j, p) in enumerate(nonzero_ps)
r = sim[p]
low, high = wilson95(r.undetected, r.packets)
plot!(rare_plot, [p, p], [low, high]; color = :orangered, lw = 2,
label = j == 1 ? "95% интервал Уилсона" : "")
end
scatter!(rare_plot, nonzero_ps,
[sim[p].undetected / sim[p].packets for p in nonzero_ps];
color = :orangered, marker = :diamond, ms = 6, label = "не обнаружено, модель")
scatter!(rare_plot, zero_ps,
[wilson95(0, sim[p].packets)[2] for p in zero_ps];
color = :orangered, marker = :dtriangle, ms = 7,
label = "0 событий: верхняя 95% граница")
println("p событий ожидается 95% интервал для доли теория внутри")
for p in ps
r = sim[p]
low, high = wilson95(r.undetected, r.packets)
expected = r.packets * theory(p).undetected
@printf("%-7g %6d %7.3f [%.3g, %.3g] %s\n",
p, r.undetected, expected, low, high,
low <= theory(p).undetected <= high ? "да" : "нет")
end
@assert all(p -> begin
r = sim[p]
low, high = wilson95(r.undetected, r.packets)
low <= theory(p).undetected <= high
end, ps)
plot(main_plot, rare_plot; layout = (2, 1), size = (1050, 760))
.png)
Модель согласуется с точной теорией в пределах статистической погрешности. Верхняя панель показывает совпадение долей верных и обнаруженных пакетов. На нижней панели интервалы вокруг ненулевых оценок содержат теоретическую кривую, а таблица подтверждает это для всех восьми точек.
При , и точная теория ожидает соответственно около , и необнаруженного пакета из . Вероятность получить ноль событий при составляет . Поэтому нулевые счётчики не противоречат теории: для таких нужно гораздо больше пакетов.
При модель дала против теоретических (около ожидаемых событий). Интервал неопределённости включает теоретическое значение. При точное значение , модель дала около .
Веб-приложение на Genie Framework
Genie Framework — набор пакетов для создания веб-приложений:
Genie.jl— веб-сервер с маршрутизацией запросов, отдачей HTML и JSON;Stipple.jl— реактивный интерфейс, связывающий переменные скрипта с элементами страницы;GenieFramework.jl— общий пакет, который подключает всё сразу и даёт макрос@genietools.
Engee запускает приложения Genie в облаке: команда engee.genie.start(папка) поднимает сервер из файла app.jl в указанной папке и возвращает адрес страницы. Код приложения выполняется в отдельном процессе. Чтобы выполнить команду в основной сессии Engee, где загружена модель, служит функция engee.genie.eval(строка_кода).
Приложение этого примера лежит в папке resources/CRCApp:
index.html— страница с полями параметров опыта: размер блока, вероятность ошибки, полином, пределы остановки и seed. Кнопки запускают опыт, очищают историю и выгружают CSV. История хранится вsessionStorageвкладки браузера.- Маршрут
/вapp.jlотдаёт эту страницу как есть. Интерфейс написан на чистом JavaScript, поэтому реактивная модель Stipple здесь не нужна. - Маршрут
POST /api/runпринимает параметры в JSON и проверяет каждое поле функциейvalidate_request. Затем он вызываетengee.genie.eval("crc_run_json(...)"): модель запускается в основной сессии, а счётчики возвращаются странице. - Блокировка
ReentrantLockне даёт запустить второй опыт, пока идёт первый. - Ввод пользователя никогда не исполняется как код: в основную сессию передаётся только проверенная строка JSON в виде строкового литерала.
Каждая строка таблицы в приложении — результат реального запуска модели crc_error_detection.engee, а не аналитический расчёт. Запустим приложение. Файл start.jl подключает функции управления, открывает модель и вызывает engee.genie.start.
include(joinpath(resources_dir, "julia", "start.jl"))
app_url = match(r"https://[^\s']+?/genie/CRCApp/", repr(crc_app_status))
println("Приложение запущено: ", isnothing(app_url) ? crc_app_status : app_url.match)
Ячейка выводит адрес приложения вида https://engee.com/prod/user/<имя_пользователя>/genie/CRCApp/. Откройте его в браузере. Так выглядит форма параметров опыта:
.png)
После запуска модели результат появляется в таблице. На снимке ниже — опыт с исходными параметрами: пакетов при . Доля верных пакетов совпадает с теоретической . Модель после запуска остаётся открытой для следующих опытов в скрипте и в приложении.
.png)
Последняя ячейка возвращает краткую сводку для точки .
th = theory(0.1); r = sim[0.1]
string("CRC ok; p=0.1: correct=", round(r.correct / r.packets, digits = 4), " (theory ", round(th.correct, digits = 4),
"), undetected=", round(r.undetected / r.packets, sigdigits = 3), " (theory ", round(th.undetected, sigdigits = 3), ")")
Вывод
Мы исследовали обнаружение ошибок с помощью CRC на модели Engee из библиотечных блоков и сравнили результаты моделирования с точной теорией. Код с полиномом и длиной пакета бит гарантированно обнаруживает одиночные и двойные ошибки, так как его минимальный вес , а также пакеты ошибок длиной до бит. Доли верных, обнаруженных и необнаруженных пакетов совпали с теорией, рассчитанной по весовому спектру кода, во всём диапазоне от до . При CRC пропускает около пакетов, а в полностью зашумлённом канале — . Вероятность пропуска ошибки определяется степенью полинома и его весовым спектром, поэтому в надёжных системах применяют полиномы большей степени.
Такой подход — модель, программные проверки, сравнение с теорией и интерактивное приложение — удобен и для лабораторных работ, и для инженерной оценки систем с обнаружением ошибок.