エンコーディング/エラー訂正チャレンジ

Question

最初の 4 バイトのメッセージを 8 バイトにエンコードし、8 バイトのうちの 1 つが完全に欠落し、もう 1 つが間違っている場合に最初の 4 バイトのメッセージを再構築することは数学的に可能ですか?再送信する方法がなく、ドロップされたバイトの位置もわかりません。

DDDDPPPP など、4 つの「データ」バイトの末尾に 4 つの「パリティ」バイトを付加するリード ソロモン エラー訂正を使用すると、最終的に DDDEPPP (E はエラー) が発生し、パリティ バイトが欠落した場合、最初のメッセージを再構築する方法はないと思います（間違っている場合は修正してください）...

最初の 4 バイト メッセージに定数を乗算 (または別の数学演算を実行) し、逆数学演算のプロパティを利用してどのバイトがドロップされたかを判断するのはどうでしょうか。または、メッセージの構造に何らかの制約を課して、1 バイトおきに奇数、その他のバイトを偶数にする必要があります。

あるいは、バイトの代わりに、何らかの方法で 10 進数 8 桁にエンコードされた 4 桁の 10 進数を使用することもできます。この場合、上記と同じ状況下でエラーが検出および修正されます。再送信は行われず、ドロップされたバイトの位置は不明です。

誰かが持っているかもしれないクレイジーなアイデアを探しています...何かアイデアはありますか？

編集：

少し不自然かもしれませんが、私が解決しようとしている状況は、たとえば、重要な数字をフォームに印刷するプリンターが故障しており、それが OCR を使用する処理会社に郵送されるような状況です。フォームを読むため。OCR は完璧ではありませんが、数字だけを読み取ることで完璧に近づくはずです。プリンターの故障はさらに大きな問題になる可能性があり、整数がドロップされる可能性がありますが、どの数字がドロップされるかを知る方法はありませんが、それらは常に正しい順序で出力され、桁が入れ替わることはありません。

最初の 4 つの数字とエラー訂正番号 (つまり 1234 5678) の間に常にスペースを印刷するようにフォームを変更すると、最初の 1234 桁が省略されたのか、5678 エラー訂正桁が省略されたのかがわかるようになります。問題が解決しやすくなります。私は、アルゴリズムを介してクレジット カード番号を検証する方法とある程度似ていると考えていますが、4 桁のチャンクで検証します。

これで私が何を探しているのかが明確になるといいのですが...

Answer 1

の情報は、理論的には、多くはありませんので、「素敵」代数構造が存在しない場合には、私は、それはあなたに10の** 4コードワードのすべての方法を取得する簡潔なスキームを見つけるのは難しいことになるだろうと思われますたるみの。幸いなことに、問題はあなたがシャノンの貪欲コード・施工法を試みることができることを十分に小さい（= 3125 5 ** 5用のGF（5）を使用することができ、以下の1）が（すでに選ばれた1と競合しないコードワードを見つけます）セットに追加します。

<時間>

GF上四次多項式f（128）としてエンコードまでの35ビット。 、8つの所定のポイントX0、...、X7およびエンコード0F（X0）1F（X1）0F（×2）1F（×3）0F（×4）1F（X5）0F（X6）1F（X7）などで多項式を評価交互に0と1がMSBに格納されている場合

最上位ビットで

復号し、初見。 MSBは、インデックスのmod 2と一致しない場合は、バイトが破損していること、および/またはそれを削除することによって左にシフトされています。それの良いを想定し、（おそらく時点で複数の異なる可能な値を累積）右にシフトバック。今、私たちは多くても1つが破損しているの知らポイントで四次多項式fの少なくとも7つの評価を、持っています。私たちは今、汚職についてあらゆる可能性を試すことができます。

EDIT：bmm6oは、私の解決策の第二の部分が間違っているという主張が進んでいます。私は反対します。

レッツ・レビューのMSBが0101101.と仮定Xが送信されたバイトの配列であり、Yは、受信したバイト配列である場合の可能性。一方、Y [0]、Y [1]、Y [2]には、Y [3]は正しいのMSBを有し、X [0]、X [1]、X [2]、X [3]であると推定されています。一方、Y [4]、Y [5]、Y [6]誤っつのMSBを有し、X [5]であると推定され、X [6]、X [7]。

X [4]が削除された場合は、

、我々は、Fの7正しい評価を持っています。

X [3]がドロップされ、X [4]が破損している場合は、

、我々は3で誤った評価を有する、6件の正しい評価

X [5]がドロップされ、X [4]が破損している場合は、

、我々は5で間違った評価を有する、6件の正しい評価

これら以外にも多くの可能性がありますが、我々は、Fを回復するのに十分でおり、6未満の正しい評価を持っていることはありません。

Answer 2

何を勉強する必要があると思いますか 消去コード 提案してくれるかも知れません。私自身も限界はわかりませんが、おそらくある種の MDS コードでこれを達成できるかもしれません。

編集：簡単な検索の後、見つけました RSコード 図書館とその中で 例 それはそう言う

In general, with E errors, and K erasures, you will need
* 2E + K bytes of parity to be able to correct the codeword
* back to recover the original message data.

したがって、リードソロモンコードが確かに答えであるように見え、実際に8,4コードの1つの消去と1つのエラーから回復できる可能性があります。

Answer 3

2つの異なるデータバイトがエラーまたは損失の影響を受けていないように、

はパリティ符号であれば動作していれば、パリティバイトが失われているときにエラー任意のデータバイトに等しくないとして、私見。

Answer 4

誤り訂正符号は、一般的なハンドル消去にすることができるが、文献に消失の位置が知られているものとします。正しいデータがチャネルから取得することができ、低自信があるときほとんどの場合、消去は復調器によって導入されます。信号は明確0または1でない場合、例えば、装置は、データが失われたことを示すのではなく、エラーの導入を危険にさらすことができます。消去は、本質的に知られている位置との誤差であるので、彼らは修正する方がはるかに簡単です。

私は必ず単一の値を失うことができますし、まだ残りの値が正しい順序で配信されることを確信することができる場所あなたの状況が何であるかないんだけど、それは、古典的な状況ではありません理論アドレスをコーディングます。

何algorithmist上記示唆されてこれです：あなたは情報のわずか7ビットに自分自身を制限することができれば、あなたが不足しているバイトの配置を知ることができるようになります0と1を交互に各バイトの8番目のビットを、埋めることができます。つまり、バイト0、2、4、6の高ビット等の高いビット1に0を置きます。あなたが唯一の7つのバイトを受信した場合、受信側では、行方不明1はバイトその高いビット一致の間から落ちてきたでしょう。残念ながら、それは非常に適切ではありません：消去とエラーが隣接している場合は、ドロップされたバイト、すぐに知ることができません。例えば、高ビット0101101の4バイト目を落とすから、または4バイトの誤りに起因すると3を落とす、または4バイトの誤りから及び5を落とす可能性があります。

あなたは、線形コードを使用することができます

1 0 0 0  0 1 1 1
0 1 0 0  1 0 1 1
0 0 1 0  1 1 0 1
0 0 0 1  1 1 1 0

（あなたが添加はして実装されている（A、B、C、D、B + C + D、+ C + D、+ B + D、+ B + C）（のようなデータをお送りしますつまり、 XORは、A、B、C、DためGF（128）））の要素です。それはシングルバイトの誤りを訂正することができますので、それは、距離4との線形コードです。あなたは症候群に復号化して復号化し、コードので、マトリックス自己双対であることができますHは上記と同じになります。

ドロップバイトがあります場合は、あなたはそれがあるかを判断するために、上記の技術を使用することができます。与えられたことにバイトをドロップすることによって作成された「パンクチャー」のコード - あなたは本質的に異なるコードをデコードしている、と判断したら。パンクしたコードは依然として線形であるので、あなたはエラーを決定するためにデコードシンドロームを使用することができます。あなたは、短縮コードのそれぞれについて、パリティ検査行列を計算しなければならないが、あなたは、この時間の控えを行うことができます。それは、任意の単一バイトのエラーを訂正できるように、短縮コードは、距離3を有している。

Answer 5

二桁で、あなたが00〜99を得、3奇数/偶数/奇数の数字で表すことができる - オンを想定桁の場合には、

は、奇数秒桁も、3桁目、等、奇数の最初の数字で行きます（125の総組み合わせ） - = 101 00 = 103 01 = 181 20 = 789 99、等合計6桁に1つのエンコード桁の二組は、最後の2桁が2の第1のセットについての事を意味するので数字やある種のチェックサム...最後の数字の隣に、私が思うには、最初の2桁の最初のメッセージ（1 =も、最初の2桁、3 =奇数最初の二つのそれぞれに奇数/偶数指標のいくつかの並べ替えかもしれません桁）と奇数であることのパターンに従います。その後、最後の数字は桁が欠落していた場合、それはすぐに明らかになり、最後の桁は正しかったと仮定し修正することができ、個々の数字の合計の1のところ、その方法かもしれません。それは物事を投げるだろうが、オフの最後の2桁の1がドロップされた場合...

Answer 6

我々は間違ったバイトに1ビットエラーを想定した場合、

これは理論的に可能になりそうです。我々は間違ったビットを識別するために、間違ったバイトと3ビットを識別するためにドロップされたバイトと3ビットを識別するために3ビットを必要としています。我々は、多くの余分なビットその3倍を持っています。

我々は間違ったバイト中のビットエラーの任意の数を特定する必要がある場合は、

しかし、それは30ビットになります。 32ビットが近すぎる私の快適さのためですが、でもルックスは、32ビットで可能にすること。

しかし、私はそれを得るためにエンコードに熱い知りません。ターボ符号をお試しください！

Answer 7

実際、Krystian が言ったように、RS コードを修正すると、v+2e < (n-k) である限り、メッセージと「パリティ」バイトの両方が修正されます。v は消去の数です (位置はわかっています)。 )、e はエラーの数です。これは、エラーのみがある場合、最大 (n-k)/2 個のエラー、または (n-k-1) 個の消去 (エラー数の約 2 倍)、または両方の混合を訂正できることを意味します (「 ブラハットの記事:エラー制御コードの変換手法 そして ユニバーサルリードソロモンデコーダ).

さらに素晴らしいのは、修正が成功したことを確認できることです。シンドローム多項式に 0 の係数のみが含まれていることを確認することで、メッセージとパリティのバイトが両方とも正しいことがわかります。これを前に実行して、メッセージに修正が必要かどうかを確認することもできます。また、デコード後に確認を実行して、メッセージとパリティ バイトの両方が完全に修復されたことを確認することもできます。

限界 v+2e < (n-k) が最適であり、これ以上のことはできません (リードソロモンが最適誤り訂正符号と呼ばれるのはこのためです)。実際、特定の点まではブルートフォース手法を使用してこの制限を超えることが可能です (8 シンボルごとにさらに 1 つまたは 2 つのシンボルを獲得できます)。 リストのデコード, 、しかし、それはまだ初期段階にあるドメインであり、実際に機能する実装を私は知りません。