Gizli Kodların ve Uzay İletişiminin Arkasındaki Temel Cebir

Uzay araştırmaları muazzam bir hassasiyet gerektirir. En yakın servis istasyonundan 70 milyon mil uzağa Mars'a bir gezici indirirken verimliliği en üst düzeye çıkarmanız ve beklenmedik durumlara hazırlanmanız gerekir. Bu, uzay aracı tasarımından veri aktarımına kadar her şey için geçerlidir: Dünya'ya sabit bir 0'lar ve 1'ler akışı olarak dönen mesajların bazı hatalar içermesi kaçınılmazdır, bu nedenle değerli zamanınızı ve enerjinizi boşa harcamadan bunları tanımlayabilmeniz ve düzeltebilmeniz gerekir.

İşte burada matematik devreye giriyor. Matematikçiler bilgiyi iletmek ve depolamak için ustaca yollar icat ettiler. Şaşırtıcı derecede etkili bir yöntem şunları kullanır: Reed-Solomon kodlarıÖğrencilerin okulda öğrendikleri aynı temel cebir üzerine inşa edilmiştir. Reed-Solomon kodlarının, ortaya çıkan yüksek maliyetli hataları düzeltirken bilgilerin iletilmesine ve güvenliğinin sağlanmasına nasıl yardımcı olduğunu görmek için bir matematik dersine uğrayalım.

Art ve Zeke adlı iki öğrenci, Bayan Al-Jabr'ın matematik dersinde gizli mesajlar alışverişinde bulunuyorlar. Art, Zeke'nin 57 ve 99 rakamlarını ortaya çıkaran son notunu ortaya çıkarır. x- (3, 6) ve (3, 57) noktalarını oluşturmak için 6 ve 99'yı koordine eder. Sanat her noktayı doğrusal denklemin içine yerleştirir y = Ax + B ve aşağıdaki denklem sistemini üretir:

57 = 3A + B

99 = 6A + B

Mesajın kodunu çözmek için Art'ın çözmesi gerekiyor A ve B. İlk denklemi ikinciden çıkararak başlıyor:

Bu ortadan kaldırır B. Bu yeni denklemin her iki tarafını da 3'e bölmek Art'a şunu söylüyor: A = 14 ve bunu tekrar ilk denklemde yerine koyarsak, 57 = 3 × 14 + B, verir B = 15.

Art artık (3, 57) ve (6, 99)'dan geçen doğrunun denklemle tanımlandığını biliyor y = 14x + 15. Ama aynı zamanda Reed-Solomon kodundaki gizli mesajın katsayılarda saklandığını da biliyor. Üzerinde anlaşmaya varılan basit alfabe şifresini kullanarak Zeke'nin mesajını çözüyor: 14 "N" ve 15 "O", bu da Art'a hayır, Zeke'in bugün okuldan sonra video oyunu oynayamayacağını söylüyor.

Bu basit Reed-Solomon kodunun sırrı geometrinin iki temel gerçeğiyle başlar. Birincisi, herhangi iki noktadan geçen benzersiz bir çizgi vardır. İkincisi, katsayılar için A ve B, her (dikey olmayan) satır formda yazılabilir y = Ax + B. Bu iki gerçek birlikte, bir doğru üzerindeki iki noktayı biliyorsanız bulabileceğinizi garanti eder. A ve Bve eğer biliyorsan A ve B, çizgideki tüm noktaları biliyorsunuz. Kısacası her iki bilgi grubuna da sahip olmak, satırı bilmekle eşdeğerdir.

Reed-Solomon kodları bu eşdeğer bilgi kümelerinden yararlanır. Gizli mesaj katsayılar olarak kodlanmıştır. A ve Bve hattın noktaları parçalara bölünür; bunların bir kısmı kamuya açık olarak iletilir, bir kısmı ise özel tutulur. Mesajın şifresini çözmek için parçaları toplayıp tekrar bir araya getirmeniz yeterli. Ve bunun için gereken tek şey basit bir cebir.

Zeke'nin eserleri Sanat'a gönderdiği 57 ve 99 numaralı parçalardı. Bu numaralar mesajın halka açık kısmıdır. Art, (3, 6) ve (3, 57) noktalarını yeniden oluşturmak için bunları kendi parçaları olan 6 ve 99 ile bir araya getirdi. Burada 3 ve 6, Art ve Zeke'nin önceden anlaştıkları mesajın özel kısmını oluşturuyor.

İki nokta bir doğru üzerinde yer alır ve mesajın kodunu çözmek için sadece o çizginin denklemini bulmanız gerekir. Her noktayı içine takmak y = Ax + B doğruya ilişkin her ikisinin de doğru olması gereken iki denklemden oluşan bir sistem verir. Artık strateji basit: Sistemi çözün, satırı belirleyin ve mesajın kodunu çözün.

Cebir dersinde muhtemelen denklem sistemlerini çözmenin grafik çizme, tahmin etme, kontrol etme ve yerine koyma gibi birçok yöntemini öğrenmişsinizdir. Art, değişkenleri birer birer ortadan kaldırmak için denklemleri cebirsel olarak değiştirdiğiniz bir yöntem olan elemeyi kullandı. Bir değişkeni her ortadan kaldırdığınızda sistemin çözümü biraz daha kolaylaşır.

Diğer şifreleme düzenlerinde olduğu gibi, mesajların güvenliğini sağlayan da genel ve özel bilgilerin akıllıca birleşimidir. Zeke sınıfta 57 ve 99 numaralarını bağırarak söyleyebilirdi ve bu Art'a göndereceği mesajın güvenliğini tehlikeye atmazdı (gerçi bu onun Bayan Al-Jabr'la başını belaya sokabilirdi). Bunun nedeni, karşılık gelen özel bilgiler olmadan - x-koordinatlar 3 ve 6 — doğrunun denklemini belirlemek imkansızdır. Bu değerleri kendilerine sakladıkları sürece gizli mesajlarını kamuoyuna güvenle iletebilirler.

Çizgi y = 14x + 15, iki harfli "hayır" kelimesini iletmek için iyidir, peki ya öğrenciler daha uzun bir sırrı paylaşmak isterlerse? Cebirin, geometrinin ve doğrusal denklem sistemlerinin tüm gücünün devreye girdiği yer burasıdır.

Diyelim ki Zeke, Art'ın yarınki İngilizce sınavında ne yapacağını düşündüğünü bilmek istiyor. Art, üç harfli cevabını 14, 59 ve 82 sayılarına dönüştürüp Zeke'ye aktarıyor. Öğrenciler, 3 uzunluğundaki Reed-Solomon kodlarını kullanırken özel sayılarının 2, 5 ve 6 olduğu konusunda önceden anlaştılar, bu nedenle Zeke, (2, 14), (5, 59) ve (6, 82).

Artık bu üç noktadan geçen doğrusal bir fonksiyon yoktur. Ancak bunu yapan benzersiz ikinci dereceden bir fonksiyon var. Ve her ikinci dereceden fonksiyon formda yazılabildiğinden y = Ax² + Bx + C, aynı genel yöntem uygulanabilir. Tek fark sistemin boyutudur.

Her noktayı içine takmak y = Ax² + Bx + C bir denklem verir, dolayısıyla üç nokta aşağıdaki üç denklemden oluşan sistemi üretir:

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

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

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

Üç bilinmeyenli üç denklemli bir sistemi çözmek, iki bilinmeyenli iki denklemli bir sistemi çözmek için biraz daha fazla çalışma gerektirir, ancak amaç aynıdır: Değişkenleri ortadan kaldırmak için denklem çiftlerini akıllıca birleştirin.

Örneğin, ilk denklemi ikinciden çıkarırsanız yeni denklem 45 = 21'i elde edersiniz.A + 3B. Aynı şekilde ikinci denklemi üçüncüden çıkarırsanız 23 = 11 elde edersiniz.A + B. Bu cebirsel işlemler yeni bir sistem üretir:

45 = 21A + 3B

23 = 11A + B

Artık "ikiye iki" sisteminiz var: iki bilinmeyenli iki denklem. Bunu çözmek için ikinci denklemi -3 ile çarpıp ilk denkleme ekleyebilirsiniz:

Tekrarlanan elemenin, üç denklemden oluşan orijinal sistemini nasıl kolayca çözülebilecek tek bir denklem haline getirdiğine dikkat edin: A = 2. Geriye doğru çalışarak takabilirsiniz A = 2'yi ikiye iki sistemindeki denklemlerden birine yerleştirip B = 1, ve sonra her iki değeri de orijinal denklemlerden birine yerine koyarak şunu elde edin: C = 4. Zeke, 2, 1 ve 4'te basit alfabe şifresini kullandıktan sonra Art'ın yarınki İngilizce sınavında "KÖTÜ" yapacağını biliyor. En azından bol bol cebir pratiği yapıyor.

Polinom fonksiyonları hakkındaki özel bir gerçek sayesinde, Reed-Solomon kodlarını kullanarak istediğiniz uzunlukta bir mesajı iletebilirsiniz. Anahtar şudur: Herhangi bir veri verildiğinde n Düzlemdeki farklı noktalar x-Koordinatlarda benzersiz bir “derece” polinomu vardır. n - 1 bunların içinden geçiyor. Bir polinomun derecesi, ifadedeki bir değişkenin en yüksek kuvvetidir, dolayısıyla ikinci dereceden bir fonksiyon şöyledir: Ax² + Bx + C en yüksek güce sahip olduğundan 2. dereceye sahiptir x 2'dir. Ve doğrusal bir fonksiyonun derecesi 1'dir, çünkü denklemde y = Ax + B, en yüksek gücü x 1.

İlk örnekte iki noktanın benzersiz bir doğrusal veya derece-1 polinomunu belirlediği gerçeğini kullandık. İkincisinde, üç noktanın benzersiz bir derece-2 veya ikinci dereceden polinomu belirlediği gerçeğine güvendik. Ve eğer 10 uzunluğunda bir mesaj göndermek istiyorsanız, mesajı 10. derece polinom fonksiyonunun 9 katsayısı olarak kodlamanız yeterli. Fonksiyonunuzu aldıktan sonra, 10 public'i hesaplayın y-daha önce üzerinde anlaşılan 10 özel değerdeki işlevi değerlendirerek değerler x-değerler. Bunu yaptığınızda, bunları güvenle geçebilirsiniz y-Alıcınızın kodunu çözebilmesi için halka açık koordinatlar. Uygulamada, Reed-Solomon kodları bundan biraz daha karmaşıktır, daha karmaşık katsayılar ve çeviri şemaları kullanır, ancak temel fikir aynıdır.

Reed-Solomon kodları, mesajınızı güvende tutmanın yanı sıra hataları yakalamanız ve hatta düzeltmeniz için basit ve etkili yollar da sunar. Bazı bilgilerin kaybolma veya bozulma ihtimali her zaman mevcut olduğundan, veriler iletildiği veya saklandığı her zaman bu önemlidir.

Bu soruna bir çözüm, verilerin fazladan kopyalarını göndermek olacaktır. Örneğin Zeke, [14, 14] yerine [14, 15, 15, 15, 14, 15] mesajını gönderebilir. Art, mesajın her bölümünün üç kopya halinde gönderildiğini bildiği sürece mesajın kodunu çözebilir ve hataları kontrol edebilir. Aslında herhangi bir hata bulursa bunları düzeltme şansı yüksektir. Art [14, 14, 24, 15, 15, 15] alırsa, ilk üç sayının farklı olması onu bir hataya karşı uyarır ve bunlardan ikisi 14 olduğundan 24'ün muhtemelen bir olması gerektiğini tahmin edebilir. 14 de. Art, mesajın kızdırılmasını istemek yerine kod çözme işlemine devam edebilir. Bu etkili ama maliyetli bir stratejidir. Göndermek için gereken zaman, enerji ve çaba ne olursa olsun n Bu, üç kat daha fazla bilgi gerektirir.

Ancak Reed-Solomon kodlarının ardındaki matematik etkili bir alternatif sunuyor. Her veri parçasının birden fazla kopyasını göndermek yerine, fazladan bir puan gönderebilirsiniz! Eğer bu ek nokta polinomunuza uyuyorsa bilgi doğrudur. Olmazsa bir hata olmuştur.

Bunun nasıl çalıştığını görmek için ilk örnekte "HAYIR" mesajını kontrol etmek istediğinizi varsayalım. Zeke ek bilgileri gönderebilir y-koordinat 155. Onun ve Art'ın üçüncü bir özel anlaşmaya vardığını varsayarsak x-önceden koordine edin, diyelim x = 10, Art bu üçüncü noktayı kodunu çözdüğü çizgiye göre kontrol edebilir. Fişi taktığında x = 10'a y = 14x +15 ve sonucun 155 olduğunu görüyor, iletimde herhangi bir hata olmadığını biliyor.

Bu sadece çizgiler için geçerli değil. İkinci örnekte Zeke'nin "KÖTÜ"yü kontrol etmesini sağlamak için Art şunu gönderebilir: y = 25. Eğer 3'ün ekstra özel olduğu konusunda anlaştılarsa x-koordinat ver, Zeke fişi takabilir x = 3 ikinci dereceden fonksiyonuna y = 2x² + x +4 ve (3, 25) noktasının uyduğunu doğrulayın, yine sadece bir nokta daha ile hatasız bir iletim onaylayın.

Ve bu ekstra puan potansiyel olarak hataları da düzeltebilir. Bir hata tespit edilirse ve alıcı mesajı içeren polinom fonksiyonunu oluşturamazsa, bunun yerine regresyon tekniklerini kullanarak "en uygun" polinomu oluşturabilir. İstatistik sınıfındaki en iyi uyum çizgisi gibi bu da, verilen noktaların hepsinden geçmese bile, verilen noktalara en yakın şekilde uyacak şekilde matematiksel olarak belirlenen polinom fonksiyonudur. Mesajın yapısına ve ne kadar ekstra bilgi gönderdiğinize bağlı olarak, bu en uygun polinom, bozuk bilgilerden bile doğru polinomu ve dolayısıyla doğru mesajı yeniden oluşturmanıza yardımcı olabilir.

İletişimin iletilmesi ve düzeltilmesindeki bu verimlilik, NASA'nın Ay ve Mars görevlerinde neden Reed-Solomon kodlarını kullandığını açıklıyor. Ve bir sonraki denklem sisteminizi çözerken size düşünecek bir şey verir. Tahmin ettikçe çözüme giden yolu kontrol edin veya ortadan kaldırın, Reed-Solomon kodlarının gücünü ve zarafetini ve sisteminizin açığa çıkarabileceği tüm sırları düşünün.

Egzersizler

1. Art, sınıfta kullandıkları şemanın aynısını kullanarak, Zeke'in kodunu çözmesi için 33 ve 57 numaralı halka açık numaraları yayınlıyor. Mesaj nedir?

2. Art ve Zeke kendi özel sayılarından elde edilen denklem sisteminin doğru olduğundan nasıl emin olabilirler? x = 3 ve x = 6'nın her zaman bir çözümü olacak mı?

3. Art'ın İngilizce sınavıyla ilgili “KÖTÜ” mesajına yanıt olarak Zeke geri gönderir [90, 387, 534]. Sınıfta kullandıkları şemanın aynısını kullandıklarını varsayarsak mesajı nedir?

4. Lola, Reed-Solomon kodunu ve Art ile Zeke tarafından kullanılan aynı basit alfabe şifresini kullanarak size iki harfli bir mesaj artı bir hata kontrol numarası gönderir. Gizlice anlaşmıştın x- 1, 3 ve 10'u önceden koordine eder ve Lola genel numaraları iletir [27, 43, 90]. Mesaj bir hata içeriyor mu?