巡回符号わかるマン

cyclic_code.d

import std;

void main(string[] args)
{
    if (args.length < 3)
    {
        writeln("Usage: rdmd cyclic_code.d <符号長> <生成多項式>");
        writeln("example: rdmd cyclic_code.d 7 1011");
        return;
    }

    auto n = args[1].to!long;
    auto gen_polynominal = args[2].string_to_ploynominal();
    long m = args[2].length - 1;

    if (n - m < 1)
    {
        writeln("Invalid argument: n-m<1");
        return;
    }
    if (args[2][$ - 1] != '1' || gen_polynominal == -1)
    {
        writeln("Invalid argument: invalid polynominal");
        return;
    }
    BigInt[BigInt] syndromes;
    BigInt[BigInt] decode;

    auto div = syndrome((BigInt(1) << n) + 1, gen_polynominal, m, n);
    writefln!"(x^n - 1) %% g(x):\t%s\t(%s)"(div.polynominal_to_string(m-1),(div == 0)?"巡回符号":"巡回符号ではない");

    writefln!"符号長:\t%d"(n);
    writefln!"生成多項式:\t%s"(polynominal_to_string(gen_polynominal, m));
    writefln!"生成多項式の次数:\t%d"(m);
    writefln!"情報記号数:\t%d"(n - m);
    writeln("符号語:");
    foreach (BigInt x; BigInt(0) .. BigInt(1) << n - m)
    {
        auto u = encode(x, gen_polynominal, m);
        decode[u & ((BigInt(1) << n) - 1)] = x;
        writefln!"\t%s:\t%s"(polynominal_to_binary_string(x, n - m - 1),
                polynominal_to_binary_string(u, n - 1));
    }
    writeln("シンドローム:");
    syndromes[BigInt(0)] = BigInt(0);
    foreach (i; 0 .. n)
    {
        auto e = BigInt(1) << i;
        auto s = syndrome(e, gen_polynominal, m, n);
        syndromes[s & ((BigInt(1) << m) - 1)] = e;

        writefln!"\t%s:\t%s"(polynominal_to_binary_string(e, n - 1),
                polynominal_to_binary_string(s, m - 1));
    }

    writeln();
    writeln("復号(インタラクティブ):");
    while (true)
    {
        write("enter> ");
        auto str = readln().chomp();
        auto u = str.string_to_ploynominal();
        if (str.length != n)
        {
            writefln!"\tInvalid input: length != %d"(n);
            continue;
        }
        if (u == -1)
        {
            writeln("\tInvalid input: invalid polynominal");
            continue;
        }
        writefln!"\t%s:\t%s"(polynominal_to_binary_string(u, n - 1), polynominal_to_string(u, n - 1));
        auto s = syndrome(u, gen_polynominal, m, n);
        writefln!"\tシンドローム:\t%s\t(%s)"(polynominal_to_binary_string(s,
                m - 1), polynominal_to_string(s, m - 1));
        if (div == 0)
        {
            auto e = syndromes[(s & ((BigInt(1) << m) - 1))];
            writefln!"\t誤り位置:\t%s\t(%s)"(polynominal_to_binary_string(e,
                    n - 1), polynominal_to_string(e, n - 1));
            writefln!"\t訂正結果:\t%s\t(%s)"(polynominal_to_binary_string(u ^ e,
                    n - 1), polynominal_to_string(u ^ e, n - 1));
            if ((u ^ e) in decode)
            {
                writefln!"\t復号結果:\t%s\t(%s)"(polynominal_to_binary_string(decode[u ^ e],
                        n - m - 1), polynominal_to_string(decode[u ^ e], n - m - 1));
            }
        }
        else if (s == 0)
        {
            writefln!"\t復号結果:\t%s\t(%s)"(polynominal_to_binary_string(decode[u],
                    n - m - 1), polynominal_to_string(decode[u], n - m - 1));
        }
        else
        {
            writeln("\t復号結果:\t誤り検出");
        }
    }
}

BigInt string_to_ploynominal(string str)
{
    auto ret = BigInt(0);
    foreach (i; 0 .. str.length)
    {
        if (str[i] == '1')
        {
            ret |= BigInt(1) << i;
            continue;
        }
        if (str[i] == '0')
            continue;

        return BigInt(-1);
    }
    return ret;
}

string polynominal_to_string(BigInt x, long degree)
{
    if (x == 0)
        return "0";
    string[] result;
    foreach (i; 0 .. degree + 1)
        if ((x & (BigInt(1) << i)) != 0)
        {
            result ~= format!"x^%d"(i);
        }
    return result.join(" + ").text;
}

string polynominal_to_binary_string(BigInt b, long degree)
{
    if (b == 0)
        return cycle("0").take(max(1, degree + 1)).text;
    string ret;
    foreach (i; 0 .. degree + 1)
    {
        ret ~= (b & 1).text;
        b >>= 1;
    }
    return ret;
}

BigInt encode(BigInt x, BigInt gen_polynominal, long m)
{
    auto ret = BigInt(0);
    foreach (i; 0 .. m + 1)
    {
        if ((gen_polynominal & 1) != 0)
        {
            ret ^= (x << i);
        }
        gen_polynominal >>= 1;
    }
    return ret;
}

BigInt syndrome(BigInt u, BigInt gen_polynominal, long m, long n)
{
    foreach_reverse (i; 0 .. n - m + 1)
        if ((u & (BigInt(1) << m + i)) != 0)
        {
            u ^= (gen_polynominal << i);
        }
    return u;
}