奇妙な通信チャネルがあり、チャネル内の特定のシーケンスを排除するだけでなく、エラーを検出する必要があります。
各メッセージの長さは 12 ビットで、3 つのニブル (それぞれ 4 ビット) に分割されます。これから少なくとも 450 の異なるコードを抽出する必要があるため、最大 3 のハミング距離を得ることができます。
ただし、シーケンス内の 2 つのニブルを同じにすることはできないため、次のシーケンスは無効です。
0xf 0xf 0xf - Three of the same nibbles in sequence
0x8 0x8 0x0 - Two of the same nibbles in sequence
0xf 0x3 0x3 - Two of the same nibbles in sequence
さらに、メッセージは途切れることなく相互に続くことができるため、1 つのシーケンスの開始に、最後のシーケンスの終了と同じ最初のニブルを含めることはできません。
0x327 0x743 - Even though they are not in the same message, two sequential nibbles are the same in the message stream
ただし、次のシーケンスは問題ありません。
0x1 0x2 0x1 - Two nibbles same, but separated by another nibble
0x0 0x1 0x2 - All nibbles different
0xf 0x8 0x3 - All nibbles different
そして、次の一連のメッセージは問題ありません。
0x121 0x012 0xf83 - No two adjacent nibbles are the same is the stream of messages
私が最初に考えたのは、メッセージに 9 ビットを使用し、各ニブルの上位ビットとして 3 つの 3 ビット部分に分割することです。
mmmc mmmc mmmc - Each character is a bit, m bits are message, c bits are checksum/parity/etc
c次に、面倒なシーケンスを排除しながらハミング距離を作成する3 ビットを埋める 512 エントリ テーブルを設計します。
ただし、これはローエンドの組み込みプロセッサで実行されます。算術演算を使用cしてオンザフライでビットを生成できれば、(プロセッサ時間を増やす代わりに) メモリを節約でき、この場合はより価値があります。
テーブルなしでこの問題を解決するために実行できるちょっとした数学はありますか?
あるいは、要件を満たす数学を使用した別のパッキング方法はありますか?