@WandererEngposted at 2022-12-27

マンチェスタ符号の高速な復号について

Q&A

Closed

解決したいこと

組込ソフトにて、マンチェスタ符号化された通信データの解析を実行させることを考えています。
二進数0b01を1、0b10を0とするマンチェスタ符号があったとき、これをソフトウェアで高速に復号するやり方を教えていただきたいです。
C/C++だとありがたいですが、その他のコード、アルゴリズムだけでも回答いただけるとありがたいです。

詳細

素直に実施すると、2ビットごとに0か1かを判定し、ビット数の1/2回ループしていく手順が考えられます。しかし、データ数が多いためこれだと時間がかかってしまいます。

ビットカウント等は高速に実施するアルゴリズムが知られていますが、同様のものがあれば教えていただきたいと思った次第です。よろしくお願いいたします。

例

下記のような変換を、高速に行いたいです。
下記は入力8ビットの例ですが、実際は32ビットごとに復号することを考えています。

入力 0b 0110 0110 → 復号結果 0b 1010
入力 0b 0101 1010 → 復号結果 0b 1100

下記のようなパターンはマンチェスタ符号としてはあり得ないので、結果どうなってもOKです。

0b 1100 0000 → 結果問わず

1Answer

@ozwk posted at 2022-12-28

0始まりで偶数番目のbitを抜き出すとして適当に考えてみました

#include <stdio.h>
#include <stdint.h>

uint32_t encode(uint16_t x){
    uint32_t ret = 0;
    for(int i=0;i<16;i++){
        ret |= ((x >> i)&1) << (2*i);
    }
    return ret;
}

uint16_t decode(uint32_t x){
    x = x & 0x55555555;
    x = ((x & 0xEEEEEEEE)>>1) | (x & 0x11111111);
    x = ((x & 0xFCFCFCFC)>>2) | (x & 0x03030303);
    x = ((x & 0xFFF0FFF0)>>4) | (x & 0x000F000F);
    x = ((x & 0xFFFFFF00)>>8) | (x & 0x000000FF);
    return x;
}

int main(void){
    printf("0x%x\n", encode(0xFFFF)); // 0x55555555
    printf("0x%x\n", decode(encode(0xFFFF))); // 0xffff
    printf("0x%x\n", decode(encode(1))); // 0x1

    for(int i=0;i<0x10000;i++){
        if(decode(encode(i)) != i){
            printf("failed:0x%x\n",i);
        }
    }
}

改良

uint16_t decode(uint32_t x){
    x = x & 0x55555555;
    x = ((x>>1)|x) & 0x33333333;
    x = ((x>>2)|x) & 0x0F0F0F0F;
    x = ((x>>4)|x) & 0x00FF00FF;
    x = ((x>>8)|x) & 0x0000FFFF;
    return x;
}

1Like

Comments

@ozwk
ただ、これを役立てるよりまえに送受信の方法を考えたほうがいい気もします。
通信周りの実際のハードウェア構成はどうなっているんでしょうか?
@WandererEng
Questioner
す、すごい！ご回答ありがとうございます。
まさに考えていたような内容です。

コメントに関しても、おっしゃる通り鋭い内容です…。
本来この手の内容はハードウェアで実施すべきと思いますが、ソフトウェアでやる必要が出てきて質問させていただきました。

マイコンボードと、ある種のデバイスをUARTでシリアル通信させていて、デバイス側には様々な機器がつながります(マイコン側はほぼ受信のみ)。
通常は特にソフトでやることもないんですが、ある特定のデバイスだけマンチェスターコードでデータを送ってくるので、それをハード変更せずに、ソフトで高速に処理する必要に迫られた…という事情です。
@ozwk
マンチェスタ符号化したデータをUARTで送ってくる輩がいるんですか……なんともまぁ……
頑張ってください。

Are you sure you want to delete the question?

マンチェスタ符号の高速な復号について

解決したいこと

詳細

例

1Answer

Comments

Your answer might help someone💌