はじめに

この前大学で「繰り返し符号」を習いました。

これはデータを送受信する際に誤りがあるかどうかを検出したり、誤りを訂正したりするための符号です。

今回はこの繰り返し符号をC++で実装し、誤り位置の検出と誤り訂正を行ってみようと思います。

なぜC++かというと、普段自分はPythonを主に使っているので、ほかの言語を扱う練習もしたほうがいいかな、と思ったからです。

(2,1)繰り返し符号

概要

(2,1)繰り返し符号は、データを2回繰り返して送信する符号です。情報ビットの$i$番目のビットを$b_i$とすると、送信ビット列は$b_1b_1b_2b_2b_3b_3...$となります。同じビットを二回繰り返すわけですね。

誤り検出の方法は簡単で、受け取ったビット列を2ビットずつ区切り、それぞれのペアでビットが一致しているかを確認すればいいです。もし一致していないペアがあれば、誤りがあると判断します。

しかし、一致していない場合、どちらのビットが誤りかはわかりません。そのため、誤り位置の検出はできても、誤り訂正はできません。

実装

では実装してみましょう。符号を作る関数と、受信した符号をデコードする関数を作ります。せっかくなのでクラスとしてまとめてみます。

class Two_RepeatCode {
    public:
        static void make(string input) {
            int length = input.length();
            for (int i = 0; i < length; i++) {
                cout << input[i] << input[i];
            }
            cout << endl;
        }
        static void decode(string input) {
            int length=input.length();
            if (length%2!=0){
                cout << "Invalid input." << endl;
                return;
            }
            bool error=false;
            for(int i=0; i<length; i+=2){
                if (input[i]!=input[i+1]){
                    cout << "Error is here. " << (i+1)/2+1 << endl;
                    error=true;
                }
            }
            if (!error) cout << "No error." << endl;
            return;
        }
};

作るほうですが、これについては受け取った文字列の各文字を2回繰り返して出力すれば良いです。最後に改行文字を入れることによって出力が一行になるわけですね。

解読する方では、受け取った文字列を2文字ずつ区切ってそれぞれを見ていきます。もし一致していないペアがあれば、推定系列のエラーがあると思われる位置を表示します。最後までエラーがなければ"No error."と表示します。複数場所のエラーにも対応しています。また、文字列の長さが奇数の場合はエラーとして扱います。

(3,1)繰り返し符号

(3,1)繰り返し符号は、データを3回繰り返して送信する符号です。情報ビットの$i$番目のビットを$b_i$とすると、送信ビット列は$b_1b_1b_1b_2b_2b_2b_3b_3b_3...$となります。同じビットを三回繰り返すわけですね。

これによって、1ビットの誤りまでなら検出・訂正が可能になります。例えば、受け取ったビット列を3ビットずつ区切ってそれぞれを見ていった結果、$101$みたいなビット列があった場合、$111$が正しいと判断し、$101$を$111$に訂正することができます。そして、その3ビットをまとめた'1'を受信系列として扱うことができるわけですね。

しかし、この方法では2ビット以上の誤りに対応することができません。例えば先ほどの場合、$000$が$101$に変化した可能性もあります。その場合受信系列は'0'になるべきですが、'1'と判断してしまったので誤り訂正になっていません。同様に、$111$が$000$に変化した場合も誤り訂正できません。むしろどこも誤っていないと判断してしまうことになります。

実装

こちらも実装してみます。

class Three_RepeatCode {
    public:
        static void make(string input) {
            int length = input.length();
            for (int i = 0; i < length; i++) {
                cout << input[i] << input[i] << input[i];
            }
            cout << endl;
        }
        static void decode(string input) {
            int length = input.length();
            if (length % 3 != 0) {
                cout << "Invalid input." << endl;
                return;
            }
            for (int i = 0; i < length; i += 3) {
                if (input[i] == input[i + 1] || input[i] == input[i + 2]) {
                    cout << input[i];
                } else if (input[i + 1] == input[i + 2]) {
                    out << input[i + 1];
                }
            }
            cout << endl;
            return;
        }
};

作る方は先ほどと同様ですね。繰り返す回数が3回になるだけです。

解読する方ですが、受け取った文字列を3文字ずつ区切ってそれぞれを見ていきます。その三つの中で多いほうのビットを受信系列として扱うわけです。多数決論理ですね。入力された系列の文字数が3の倍数でない場合はエラーとして扱います。複数のエラーがあっても、それぞれ1ビットの誤りならしっかりと訂正できます。

使ってみる

これらの関数を扱うために、以下のようなmain関数を書いてみました。

int main(void){
    string input;
    int number;
    string select;
    cin >> input;
    cin >> number;
    cin >> select;
    for (int i = 0; i < input.length(); i++) {
        if (input[i] != '0' && input[i] != '1') {
            cout << "Invalid input." << endl;
            return 0;
        }
    }
    if (number == 2) {
        if (select == "make") Two_RepeatCode::make(input);
        else if (select == "decode") Two_RepeatCode::decode(input);
        else cout << "Invalid select." << endl;
    }
    else if (number == 3) {
        if (select == "make") Three_RepeatCode::make(input);
        else if (select == "decode") Three_RepeatCode::decode(input);
        else cout << "Invalid select." << endl;
    }
    else {
        cout << "Invalid number." << endl;
    }
    return 0;
}

ユーザが入力するものは符号化もしくは解読する文字列、繰り返し回数、そして符号化するか解読するかを選択する文字列です。それに応じて適切な関数を呼び出すようにしています。不正な入力があった場合はエラーメッセージを表示します。

4通りの入力に対して、それぞれ以下のような出力が得られました。

11001
2
make
1111000011

0011001
3
make
000000111111000000111

01001110
2
decode
Error is here. 1
Error is here. 4

101100011101
3
decode
1011

正しく動作できていることがわかりました。

おわりに

今回は繰り返し符号をC++で実装してみました。

学んだことをまとめ、慣れていない言語で実装してみるとかなり勉強になるということがわかったので、これからも続けていこうかなと思いました。

↓今回のリポジトリ
https://github.com/Gitudon/Test-Repositories/tree/master/Repeat-Code