秘密のコードと宇宙通信の背後にある基本的な代数

宇宙探査には途方もない精度が必要です。 最寄りのサービス ステーションから 70 万マイル離れた火星にローバーを着陸させる場合、効率を最大化し、予期せぬ事態に備える必要があります。 これは、宇宙船の設計からデータ伝送まですべてに当てはまります。0 と 1 の安定したストリームとして地球に返されるメッセージには、必ずエラーが含まれているため、貴重な時間とエネルギーを無駄にすることなくエラーを特定して修正できる必要があります。

そこで数学の出番です。数学者は、情報を送信および保存するための独創的な方法を発明しました。 驚くほど効果的な方法の XNUMX つを使用します。 リードソロモンコード、学生が学校で学ぶのと同じ基本的な代数に基づいて構築されています。 数学の授業に立ち寄って、リードソロモン コードがどのように情報を送信および保護し、発生したコストのかかるエラーを修正するかを見てみましょう。

Art と Zeke の 57 人の生徒が、Al-Jabr 先生の数学のクラスで秘密のメッセージを交換しています。 Art は Zeke の最新のメモを開き、99 と XNUMX という数字を明らかにします。 x- 座標 3 と 6 で点 (3, 57) と (6, 99) を作成します。 アートは各点を一次方程式に当てはめます y = Ax + B となり、次の連立方程式が生成されます。

57 = 3A + B

99 = 6A + B

メッセージを解読するために、アートは以下を解決しなければなりません A & B. 彼は、最初の式を XNUMX 番目の式から引くことから始めます。

これは排除します B. この新しい式の両辺を 3 で割ると、Art は次のことを伝えます。 A = 14、これを最初の式に戻すと、57 = 3 × 14 + B、与える B = 15。

Art は、(3, 57) と (6, 99) を通る直線が次の式で記述されることを知っています。 y = 14x + 15. しかし、リードソロモン符号では、秘密のメッセージが係数に隠れていることも知っています。 彼は、合意された単純なアルファベット暗号を使用してジークのメッセージを解読します。14 は「N」、15 は「O」です。アートは、ジークが今日の放課後にビデオゲームをプレイできないことを伝えます。

この単純なリードソロモン コードの秘密は、幾何学の XNUMX つの基本的な事実から始まります。 まず、任意の XNUMX 点を通る唯一の直線があります。 第二に、係数について A & B、すべての（非垂直）行は次の形式で記述できます y = Ax + B. これら XNUMX つの事実が合わさると、直線上の XNUMX 点を知っていれば、 A & B、そしてあなたが知っているなら A & B、あなたは線上のすべての点を知っています。 つまり、どちらかの情報を持っていることは、回線を知っていることと同じです。

リードソロモン符号は、これらの同等の情報セットを利用します。 秘密のメッセージは係数としてエンコードされます A & B、およびラインのポイントは断片に分割され、一部は公開され、一部は非公開にされます。 メッセージを解読するには、断片を集めて元に戻すだけです。 これに必要なのは単純な代数だけです。

Zeke の作品は、彼が Art に送った 57 と 99 の数字でした。 これらの番号は、メッセージの公開部分です。 Art はそれらを自分の作品 3 と 6 と組み合わせて、ポイント (3, 57) と (6, 99) を再構築しました。 ここで、3 と 6 は、アートとジークが事前に合意したメッセージのプライベート部分を構成します。

XNUMX つの点は線上にあり、メッセージを解読するには、その線の方程式を見つける必要があります。 各ポイントに差し込む y = Ax + B は、両方とも真でなければならない直線に関する XNUMX つの方程式系を与えます。 戦略は簡単です。システムを解決し、行を決定し、メッセージを解読します。

代数のクラスでは、おそらく、グラフ化、推測とチェック、代入など、連立方程式を解くための多くの方法を学んだでしょう。 アートは消去法を使用しました。これは、変数を XNUMX つずつ消去するために方程式を代数的に操作する方法です。 変数を削除するたびに、システムの解決が少し簡単になります。

他の暗号化スキームと同様に、メッセージを安全に保つのは公開情報と非公開情報の巧妙な組み合わせです。 Zeke は自分の番号 57 と 99 を教室全体で大声で叫ぶことができ、Art へのメッセージのセキュリティが危険にさらされることはありませんでした (Ms. Al-Jabr とトラブルになる可能性はありますが)。 これは、対応する個人情報がないためです。 x-座標 3 と 6 — 直線の方程式を特定することは不可能です。 これらの値を自分自身に保持している限り、秘密のメッセージを安全に公開できます。

この線 y = 14x + 15 は「いいえ」という XNUMX 文字の単語を送信するのに適していますが、生徒がより長い秘密を共有したい場合はどうすればよいでしょうか。 ここで、代数、幾何学、線形方程式系の能力がフルに発揮されます。

Zeke が Art が明日の英語のテストで自分がどうなると思うか知りたがっているとします。 アートは彼の 14 文字の答えを 59、82、3 の数字に変換し、それらを Zeke に渡します。 生徒たちは、長さ 2 のリードソロモン コードを使用する場合、個人番号は 5、6、および 2 であることに事前に同意したため、Zeke はそれらのピースを組み合わせて点 (14, 5)、(59, 6)、および (82, XNUMX)。

さて、これらの XNUMX 点を通る線形関数はありません。 しかし、それを行うユニークな二次関数があります。 また、すべての二次関数は次の形式で記述できるため、 y = Ax² + Bx + C、同じ一般的な方法を適用できます。 唯一の違いは、システムのサイズです。

各ポイントに差し込む y = Ax² + Bx + C は XNUMX つの方程式を生成するため、XNUMX つの点から次の XNUMX つの方程式系が生成されます。

(2, 14): 14 = 4A + 2B + C

(5, 59): 59 = 25A + 5B + C

(6, 82): 82 = 36A + 6B + C

XNUMX つの未知数を持つ XNUMX つの連立方程式を解くには、XNUMX つの未知数を持つ XNUMX つの連立方程式よりも少し多くの作業が必要ですが、目標は同じです: 方程式のペアを巧みに組み合わせて変数を削除します。

たとえば、最初の式を 45 番目の式から引くと、新しい式 21 = XNUMX が得られます。A + 3B. 同様に、23 番目の式から 11 番目の式を引くと、XNUMX = XNUMX になります。A + B. これらの代数操作により、新しいシステムが生成されます。

45 = 21A + 3B

23 = 11A + B

これで、「3 x XNUMX」システム、つまり XNUMX つの未知数を持つ XNUMX つの方程式ができました。 これを解くには、XNUMX 番目の方程式に −XNUMX を掛けて、最初の方程式に追加します。

消去を繰り返すことで、元の XNUMX つの連立方程式が簡単に解ける XNUMX つの方程式に変わったことに注目してください。 A = 2.逆方向に作業すると、プラグインできます A = 2 を XNUMX 行 XNUMX 列の方程式の XNUMX つに代入して、 B = 1 とし、両方の値を元の方程式の XNUMX つに代入して、 C = 4. 2、1、4 で単純なアルファベット暗号を使用した後、Zeke は Art が明日の英語のテストで「BAD」を出すことを知っています。 少なくとも彼は代数の練習をたくさん積んでいます。

多項式関数に関する特別な事実のおかげで、リードソロモン コードを使用して任意の長さのメッセージを送信できます。 鍵はこれです: n 異なる面内の点 x-座標には、「次数」という固有の多項式があります n - それらを通過する 1。 多項式の次数は、式の変数の最大べき乗であるため、次のような二次関数 Ax² + Bx + C 次数が 2 です。 x は 2 です。線形関数の次数は 1 です。 y = Ax + B、最高のパワー x 1です。

最初の例では、1 つの点が一意の線形または次数 2 の多項式を決定するという事実を使用しました。 10 つ目は、10 つの点が固有の 9 次多項式 (二次多項式) を決定するという事実に依存していました。 長さ 10 のメッセージを送信する場合は、メッセージを次数 XNUMX の多項式関数の XNUMX 個の係数としてエンコードするだけです。 関数を作成したら、XNUMX public を計算します y-事前に合意された10個のプライベートで関数を評価することによる値 x-値。 それをしたら、安全にそれらを渡すことができます y-受信機がデコードできるように公開されている座標。 実際には、Reed-Solomon コードはこれよりも少し複雑で、より洗練された種類の係数と変換スキームを利用していますが、基本的な考え方は同じです。

メッセージを安全に保つだけでなく、Reed-Solomon コードは、エラーを見つけて修正するための簡単で効率的な方法も提供します。 情報の一部が失われたり破損したりする可能性が常にあるため、これはデータが送信または保存されるときはいつでも重要です。

この問題の解決策の 14 つは、単純にデータの余分なコピーを送信することです。 たとえば、Zeke は [14, 14] の代わりに [15, 15, 15, 14, 15, 14] というメッセージを送信できます。 Art は、メッセージのすべての部分が 14 通で送信されることを知っている限り、メッセージをデコードしてエラーをチェックできます。 実際、エラーを見つけた場合は、修正できる可能性が高くなります。 Art が [24, 15, 15, 15, 14, 24] を受け取った場合、最初の 14 つの数字が異なるという事実が彼にエラーを警告し、そのうちの XNUMX つが XNUMX であるため、Art は XNUMX がおそらくXNUMXも。 メッセージの再送信を求める代わりに、Art は解読を続行できます。 これは効果的ですが、費用のかかる戦略です。 発信するのにどんなに時間、エネルギー、労力が必要でも n これには XNUMX 倍の情報が必要です。

しかし、Reed-Solomon コードの背後にある数学は、効率的な代替手段を提供します。 すべてのデータの複数のコピーを送信する代わりに、余分なポイントを XNUMX つ送信するだけで済みます。 その追加の点が多項式に適合する場合、情報は正しいです。 そうでない場合は、エラーが発生しています。

これがどのように機能するかを確認するために、最初の例のメッセージ「NO」を確認したいとします。 Zeke は追加の y-coordinate 155. 彼と Art が XNUMX 番目のプライベートで合意したと仮定すると、 x-事前に調整して、言う x = 10、Art はこの XNUMX 番目の点を自分がデコードした行と照合できます。 彼がプラグインするとき x = 10 に y = 14x + 15 で、結果が 155 であることを確認すると、送信にエラーがなかったことがわかります。

これは行だけでは機能しません。 XNUMX 番目の例で Zeke が「BAD」をチェックできるようにするために、Art は送信できます。 y = 25. 3 がエクストラ プライベートであることに同意した場合 xコーディネイト、ジーク缶プラグ x = 3 を二次関数に y = 2x² + x + 4 でポイント (3, 25) が適合することを確認し、もう XNUMX つのポイントでエラーのない送信を確認します。

そして、その余分なポイントにより、エラーも修正される可能性があります。 エラーが検出され、受信側がメッセージを含む多項式関数を構築できない場合、代わりに回帰手法を使用して「最適な」多項式を構築できます。 統計クラスの最適線のように、これは、すべての点を通過しない場合でも、指定された点に最もよく適合するように数学的に決定される多項式関数です。 メッセージの構造と、送信する追加情報の量に応じて、この最適な多項式は、正しい多項式を再構築するのに役立ちます。つまり、正しいメッセージを、破損した情報からでも再構築できます。

通信の送信と修正におけるこの効率性は、NASA が月と火星へのミッションでリードソロモン コードを使用した理由を説明しています。 そして、次の連立方程式を解くときに、熟考する何かを与えてくれます。 ご想像のとおり、ソリューションへの道をチェックまたは排除し、Reed-Solomon コードのパワーとエレガンス、およびシステムが明らかにする可能性のあるすべての秘密について考えてみてください。

演習

1. 授業で使用したのと同じスキームを使用して、アートは公開番号 33 と 57 を公開し、ジークが解読できるようにします。 メッセージは何ですか？

2. Art と Zeke はどうすれば、自分たちの個人番号から得られる連立方程式が正しいことを確認できますか? x = 3と x = 6 は常に解決策を持っていますか?

3. Art の英語のテストに関する「BAD」のメッセージに対して、Zeke は返信します [90, 387, 534]。 彼らがクラスで使用したのと同じスキームを使用すると仮定すると、彼のメッセージは何ですか?

4. Lola は、XNUMX 文字のメッセージと、Reed-Solomon コードと、Art と Zeke が使用するのと同じ単純なアルファベット暗号を使用して、XNUMX つのエラー チェック番号を送信します。 あなたは密かに同意しました x・事前に1、3、10を座標化し、ローラが公開番号「27、43、90」を発信。 メッセージにエラーが含まれていますか?