Исследование обнаружения ошибок с помощью 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 приписывает к данным остаток от деления:

Полная длина пакета , при исходных настройках , , . Любое кодовое слово делится на без остатка.

Приёмник вычисляет синдром — остаток от деления принятого слова на . Если канал добавил вектор ошибок , синдром равен . Ошибка не обнаруживается, только если сам является ненулевым кодовым словом.

Двоичный симметричный канал независимо инвертирует каждый бит с вероятностью . Каждый пакет попадает ровно в один из трёх классов:

где — число кодовых слов веса (весовой спектр кода). При все векторов ошибок равновероятны, и доля необнаруженных ошибок равна : из векторов с нулевым синдромом нужно исключить единственный случай без ошибок. Для и это почти .

Описание модели

Модель 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

Payload                   /Communication Systems/Sources/Random Data Sources/Bernoulli Binary Generator
                          SamplesPerFrame = crc_k; ProbabilityOfZero = 0.5; InitialSeed = crc_seed; SampleTime = 1/crc_k
CRC Encoder               /Communication Systems/Error Detection And Correction/CRC/General CRC Generator
                          GeneratorPolynomial = [5 3 0]; InitialStates = 0; DirectMethod = false; ReflectInputBytes = false; FinalXOR = 0
Channel Noise             /Communication Systems/Sources/Random Data Sources/Bernoulli Binary Generator
                          SamplesPerFrame = crc_n; ProbabilityOfZero = 1 - crc_p; InitialSeed = crc_seed + 1; SampleTime = 1/crc_n
Binary Symmetric Channel  /Basic/Logic and Bit Operations/Logical Operator
                          Operator = XOR
CRC Detector              /Communication Systems/Error Detection And Correction/CRC/General CRC Syndrome Detector
                          GeneratorPolynomial = [5 3 0]; InitialStates = 0; DirectMethod = false
Data Changed              /Basic/Logic and Bit Operations/Logical Operator
                          Operator = XOR
Any Bit Changed           /Basic/Logic and Bit Operations/Logical Operator
                          Operator = OR; Inputs = 1
Undetected                /Basic/Logic and Bit Operations/Logical Operator
                          Operator = AND
Correct                   /Basic/Logic and Bit Operations/Logical Operator
                          Operator = NOR
Previous Totals           /Basic/Discrete/Unit Delay
                          InitialCondition = zeros(5); SampleTime = 1
Stop Limits               /Basic/Sources/Constant
                          Value = [crc_packet_limit, Inf, crc_error_limit, Inf, Inf]
Limit Reached             /Basic/Logic and Bit Operations/Relational Operator
                          Operator = >=

Параметры задаются переменными рабочей области. Шаг источников равен и на один бит, поэтому за шаг модели каждый источник выдаёт кадр из или бит. Параметры 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))

n    k    t    блоки Engee  полином (степени)
7    4    1    да           [3, 1, 0]
15   11   1    да           [4, 1, 0]
15   7    2    да           [8, 7, 6, 4, 0]
15   5    3    да           [10, 8, 5, 4, 2, 1, 0]
31   26   1    да           [5, 2, 0]
31   21   2    да           [10, 9, 8, 6, 5, 3, 0]
31   16   3    да           [15, 11, 10, 9, 8, 7, 5, 3, 2, 1, 0]
31   11   5    да           [20, 18, 17, 13, 10, 9, 7, 6, 4, 2, 0]
31   6    7    да           [25, 24, 21, 19, 18, 16, 15, 14, 13, 11, 9, 5, 2, 0]
63   57   1    да           [6, 1, 0]
63   51   2    да           [12, 10, 8, 5, 4, 3, 0]
63   45   3    да           [18, 17, 16, 15, 9, 7, 6, 3, 2, 1, 0]
63   39   4    да           [24, 23, 22, 20, 19, 17, 16, 13, 10, 9, 8, 6, 5, 4, 2, 1, 0]
63   36   5    да           [27, 22, 21, 19, 18, 17, 15, 8, 4, 1, 0]
63   30   6    нет          [33, 32, 30, 29, 28, 27, 26, 23, 22, 20, 15, 14, 13, 11, 9, 8, 6, 5, 2, 1, 0]
63   24   7    нет          [39, 38, 37, 36, 34, 33, 31, 28, 27, 25, 23, 22, 17, 11, 8, 5, 0]
63   18   10   нет          [45, 43, 42, 41, 40, 37, 36, 31, 29, 28, 26, 24, 21, 19, 16, 15, 14, 12, 9, 8, 7, 6, 4, 2, 0]
63   16   11   нет          [47, 46, 43, 42, 40, 39, 36, 33, 32, 27, 25, 24, 23, 22, 20, 19, 18, 16, 13, 12, 11, 9, 8, 5, 3, 1, 0]
63   10   13   нет          [53, 50, 49, 48, 46, 44, 43, 40, 37, 34, 33, 29, 27, 26, 24, 22, 20, 19, 18, 16, 14, 12, 6, 5, 3, 2, 0]
63   7    15   нет          [56, 54, 52, 49, 48, 45, 41, 38, 36, 35, 33, 32, 28, 27, 26, 24, 19, 18, 16, 14, 13, 12, 9, 8, 7, 6, 4, 3, 2, 1, 0]
Поддерживается 14 из 20 полиномов

Столбец — число ошибок, которое исправлял бы соответствующий код БЧХ. Модель только обнаруживает ошибки, поэтому приведено как справка. Доступны все коды длины , и и пять кодов длины . Шесть кодов длины с полиномами степени от до библиотечные блоки 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

Всего 2000: верно 270, обнаружено 1720, не обнаружено 10; битовых ошибок 3779; Достигнут предел пакетов; 31.0 с

За пакетов при верно принято пакетов, ошибочных пакетов обнаружено и пропущено. Это количество пакетов, а не бит: в канале было инвертировано бит из , то есть при ожидаемых . Доля верных пакетов совпадает с теоретической . Сумма трёх классов равна числу переданных пакетов, эту проверку выполняет @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

Все проверки пройдены: true
  no noise                                         n=19  p=0    пакетов 1000  верно 1000  обн. 0     не обн. 0
  undetected limit                                 n=7   p=1    пакетов 5     верно 0     обн. 0     не обн. 5
  all inverted detected                            n=19  p=1    пакетов 31    верно 0     обн. 31    не обн. 0
  repeatable noise                                 n=19  p=0.1  пакетов 2000  верно 270   обн. 1720  не обн. 10
  CRC Generator block versus independent polynomial division кадров 32, одиночных ошибок 19
  degree 27 source polynomial                      n=63  p=0    пакетов 64    верно 64    обн. 0     не обн. 0

Все проверки пройдены:

без шума все пакетов приняты верно;
для кода инверсия всех бит превращает кодовое слово в другое кодовое слово: слово из семи единиц делится на . 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

Весовой спектр A_w (w: число слов): 0:1  3:32  4:132  5:368  6:840  7:1544  8:2358  9:2952  10:2896  11:2288  12:1572  13:896  14:360  15:104  16:33  17:8
Минимальный ненулевой вес d_min = 3

theory (generic function with 1 method)

Минимальный вес ненулевого кодового слова , поэтому 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

p = 0.001 верно 0.9814 (теор. 0.9812)  обн. 0.0186 (0.0188)  не обн. 0.00e+00 (3.16e-08)
p = 0.003 верно 0.9436 (теор. 0.9445)  обн. 0.0563 (0.0555)  не обн. 0.00e+00 (8.34e-07)
p = 0.01  верно 0.8286 (теор. 0.8262)  обн. 0.1714 (0.1738)  не обн. 0.00e+00 (2.84e-05)
p = 0.03  верно 0.5623 (теор. 0.5606)  обн. 0.4370 (0.4388)  не обн. 6.50e-04 (6.05e-04)
p = 0.1   верно 0.1323 (теор. 0.1351)  обн. 0.8588 (0.8552)  не обн. 8.85e-03 (9.75e-03)
p = 0.2   верно 0.0129 (теор. 0.0144)  обн. 0.9613 (0.9607)  не обн. 2.57e-02 (2.49e-02)
p = 0.3   верно 0.0009 (теор. 0.0011)  обн. 0.9682 (0.9685)  не обн. 3.08e-02 (3.03e-02)
p = 0.5   верно 0.0000 (теор. 0.0000)  обн. 0.9682 (0.9688)  не обн. 3.18e-02 (3.12e-02)

Доли верных и обнаруженных пакетов совпадают с теорией до второго-третьего знака во всём диапазоне. Необнаруженные ошибки — редкое событие, и при малых модель не зарегистрировала ни одного. Чтобы понять, согласуется ли это с теорией, нужна оценка статистической погрешности.

Построим две панели: доли верных и обнаруженных пакетов на обычной шкале, затем долю необнаруженных ошибок на логарифмической шкале. Для каждой ненулевой оценки покажем 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))

p       событий  ожидается  95% интервал для доли        теория внутри
0.001        0      0.001    [0, 0.000192]       да
0.003        0      0.017    [0, 0.000192]       да
0.01         0      0.568    [0, 0.000192]       да
0.03        13     12.094    [0.00038, 0.00111]       да
0.1        177    195.099    [0.00764, 0.0102]       да
0.2        515    497.190    [0.0236, 0.028]       да
0.3        617    606.646    [0.0285, 0.0333]       да
0.5        636    624.962    [0.0295, 0.0343]       да

Модель согласуется с точной теорией в пределах статистической погрешности. Верхняя панель показывает совпадение долей верных и обнаруженных пакетов. На нижней панели интервалы вокруг ненулевых оценок содержат теоретическую кривую, а таблица подтверждает это для всех восьми точек.

При , и точная теория ожидает соответственно около , и необнаруженного пакета из . Вероятность получить ноль событий при составляет . Поэтому нулевые счётчики не противоречат теории: для таких нужно гораздо больше пакетов.

При модель дала против теоретических (около ожидаемых событий). Интервал неопределённости включает теоретическое значение. При точное значение , модель дала около .

Веб-приложение на 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/demo54365636-yurev/genie/CRCApp/

Ячейка выводит адрес приложения вида https://engee.com/prod/user/<имя_пользователя>/genie/CRCApp/. Откройте его в браузере. Так выглядит форма параметров опыта:

После запуска модели результат появляется в таблице. На снимке ниже — опыт с исходными параметрами: пакетов при . Доля верных пакетов совпадает с теоретической . Модель после запуска остаётся открытой для следующих опытов в скрипте и в приложении.

Последняя ячейка возвращает краткую сводку для точки .

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 ok; p=0.1: correct=0.1324 (theory 0.1351), undetected=0.00885 (theory 0.00975)"

Вывод

Мы исследовали обнаружение ошибок с помощью CRC на модели Engee из библиотечных блоков и сравнили результаты моделирования с точной теорией. Код с полиномом и длиной пакета бит гарантированно обнаруживает одиночные и двойные ошибки, так как его минимальный вес , а также пакеты ошибок длиной до бит. Доли верных, обнаруженных и необнаруженных пакетов совпали с теорией, рассчитанной по весовому спектру кода, во всём диапазоне от до . При CRC пропускает около пакетов, а в полностью зашумлённом канале — . Вероятность пропуска ошибки определяется степенью полинома и его весовым спектром, поэтому в надёжных системах применяют полиномы большей степени.

Такой подход — модель, программные проверки, сравнение с теорией и интерактивное приложение — удобен и для лабораторных работ, и для инженерной оценки систем с обнаружением ошибок.

Исследование обнаружения ошибок с помощью CRC