Skip to content

Instantly share code, notes, and snippets.

@kotet
Last active Dec 22, 2019
Embed
What would you like to do?
巡回符号わかるマン
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment