'Sihirli' Hata Düzeltme Planının Doğası gereği Verimsiz Olduğu Kanıtlandı | Quanta Dergisi

Kısa mesaj gönderdiyseniz, CD oynattıysanız veya bulutta dosya sakladıysanız, hata düzeltmeden yararlanmışsınız demektir. Bu devrim niteliğindeki fikir, araştırmacıların herhangi bir mesajı daha sonra meydana gelebilecek yolsuzlukların kolayca tersine çevrilmesine olanak sağlayacak bir biçimde yeniden yazmanın mümkün olduğunu ilk kez fark ettiği 1940'lara kadar uzanıyor.

Yıllar geçtikçe araştırmacılar, verileri farklı şekillerde kodlayan ve hataları düzeltmek için farklı prosedürler kullanan, hata düzeltme kodları adı verilen birçok ustaca plan geliştirdiler. Ancak teorik bilgisayar bilimcileri için çok azı yerel olarak düzeltilebilir kodlar kadar ilgi çekicidir. Bu kodlar, kulağa neredeyse çelişkili gelen iki eşzamanlı özelliğe sahiptir: Herhangi bir hata, kodlanmış verinin yalnızca birkaç yerden okunmasıyla düzeltilebilir, ancak hiçbir saldırgan, koda seçici bir şekilde müdahale ederek bu düzeltme prosedürünü engelleyemez. Sanki bir kitaptan yırtılmış herhangi bir sayfayı diğer birkaç sayfaya bakarak kurtarabiliyormuşsunuz gibi.

"Bu oldukça büyülü bir olay" dedi Tom GürCambridge Üniversitesi'nde bilgisayar bilimcisi. "A priori, böyle bir matematiksel nesnenin var olabileceği hiç de açık değil."

Ancak bu sihrin çok büyük bir bedeli var. Yerel olarak düzeltilebilen kodların bilinen tek örnekleri son derece verimsizdir; herhangi bir mesajın kodlanması, mesajın katlanarak daha uzun olmasına da neden olur. Bu şekilde kodlanan kitapların tamamı fazlasıyla kullanışsız olacaktır.

Bilgisayar bilimcileri uzun zamandır daha iyi yerel olarak düzeltilebilir kodların mümkün olup olmadığını merak ediyorlardı. Bu ciddi kısıtlamanın bu kodların anlaşılmasını kolaylaştıracağını umarak özellikle herhangi bir hatayı düzeltmek için yalnızca üç sorgu kullanan kodlara odaklandılar. Ancak bu basit vaka bile 20 yılı aşkın süredir araştırmacıları şaşkına çeviriyor.

Şimdi bilgisayar bilimcisi Praveş Kothari Carnegie Mellon Üniversitesi ve yüksek lisans öğrencisi Peter Manohar sonunda var kanıtladı Bu üstel maliyeti önleyen, yerel olarak düzeltilebilir üç sorgulu bir kod oluşturmanın imkansız olduğunu. Olumsuz bir sonuç olabilir, ancak hata düzeltmenin sınırlarını netleştiren herhangi bir şey araştırmacılar için heyecan vericidir; özellikle de yerel olarak düzeltilebilir kodların matematiği iletişimden çok uzak alanlarda ortaya çıktığı için.

"Bu sonuç muhteşem" dedi Şubhangi SarafToronto Üniversitesi'nde bilgisayar bilimcisi. "Bu çok büyük bir atılım."

Rakamlarla Mukavemet

Hata düzeltmeyi anlamak için, korumak istediğiniz verileri bir dizi bit veya 0 ve 1 olarak hayal edin. Bu modelde bir hata, ister rastgele bir dalgalanmadan ister kasıtlı bir kurcalamadan kaynaklansın, 0'ın 1'e istenmeyen herhangi bir dönüşü veya tam tersi olabilir.

Diyelim ki bir arkadaşınıza mesaj göndermek istiyorsunuz ancak hataların anlamı değiştirebileceğinden endişe ediyorsunuz. Basit bir strateji, mesajınızdaki her 0'ı 000 ve her 1'i 111 ile değiştirmektir. Arkadaşınız mesajın art arda üç aynı biti içermeyen bir kısmını görürse, bir hata oluştuğunu anlayacaktır. Ve eğer hatalar rastgele ve nispeten nadir ise, o zaman 110'luk herhangi bir dizinin bozuk bir 111'den ziyade bozuk bir 000 olma olasılığı çok daha yüksektir. Her üçlü içindeki basit çoğunluk oyu çoğu hatayı düzeltmek için yeterli olacaktır.

Tekrarlama kodu olarak adlandırılan bu şema, basitlik avantajına sahiptir, ancak bunu önerecek başka pek bir şey yoktur. Öncelikle, nispeten nadir görülen hatalarla başa çıkmak için her mesajın uzunluğunu üç katına çıkarmayı gerektirir ve eğer iki bitişik hatanın oluşma ihtimali yeterliyse, daha fazla fazlalığa ihtiyacımız olacaktır. Daha da kötüsü, saldırganların aktif olarak kodu sabote etmeye çalışması gibi hatalar rastgele değilse, hızla işe yaramaz hale gelir. Tekrarlama kodunda, belirli bir biti düzeltmek için gereken tüm bilgiler yalnızca birkaç bitte depolanır ve bu da onu hedefli saldırılara karşı savunmasız bırakır.

Neyse ki birçok hata düzeltme kodu daha iyi sonuçlar veriyor. Ünlü bir örnek, Reed-Solomon kodu, mesajları polinomlara (örneğin matematiksel ifadeler) dönüştürerek çalışır x² + 3x + 2, her biri bir değişkene sahip olan farklı terimlerin bir araya getirilmesinden oluşur (örneğin x) farklı bir güce yükseltildi. Reed-Solomon kodunu kullanarak bir mesajı kodlamak, mesajdaki her karakter için bir terim içeren bir polinom oluşturmayı, ardından polinomu bir grafik üzerinde bir eğri olarak çizmeyi ve eğri üzerinde bulunan noktaların koordinatlarını saklamayı (en az bir tane daha alarak) içerir. karakter sayısından daha fazla nokta). Hatalar bu noktalardan birkaçını eğrinin dışına itebilir, ancak çok fazla hata yoksa noktaların çoğundan yalnızca bir polinom eğrisi geçecektir. Bu eğri neredeyse kesinlikle gerçek mesaja karşılık geliyor.

Reed-Solomon kodları son derece verimlidir; hataları düzeltmek için yalnızca birkaç ekstra nokta depolamanız gerekir, böylece kodlanmış herhangi bir mesaj orijinalinden yalnızca marjinal olarak daha uzun olur. Ayrıca, herhangi bir yerdeki bir hatayı düzeltmek için kullanılan bilgiler kodlanmış mesajın tamamına dağıtıldığından, tekrar kodu için felaket anlamına gelebilecek türden hedefli kesintilere karşı daha az savunmasızdırlar.

Küresel olarak, Yerel Davran düşünüyorum

Reed-Solomon kodunun gücü birbirine bağlı olmasından kaynaklanmaktadır. Ancak tam olarak bu birbirine bağlılık nedeniyle, şifrelenmiş bir mesajdaki tek bir hatayı, tamamını okumadan düzeltmenin bir yolu yoktur. İletişim bağlamında bu bir sorun gibi görünmeyebilir: Bir mesaj gönderiyorsanız muhtemelen alıcının mesajın tamamını okumasını istersiniz. Ancak hata düzeltmenin bir başka önemli uygulaması olan veri depolamada bu bir sorumluluk olabilir.

Kullanıcıların e-postalarını bulutta, yani çok çeşitli sunucularda depolayan bir şirket düşünün. E-posta koleksiyonunun tamamını tek bir uzun mesaj olarak düşünebilirsiniz. Şimdi bir sunucunun çöktüğünü varsayalım. Reed-Solomon koduyla, e-postalarınızı kayıp sunucudan kurtarmak için tüm kodlanmış verileri içeren devasa bir hesaplama yapmanız gerekir. "Her şeye bakmak lazım" dedi Zeev DvirPrinceton Üniversitesi'nde bilgisayar bilimcisi. "Bu milyarlarca ve milyarlarca e-posta olabilir; gerçekten uzun zaman alabilir."

Araştırmacılar, kodlanmış mesajın yalnızca bir kısmını kullanan kodları tanımlamak için "yerel" terimini kullanıyorlar. hataları tespit et veya bunları düzeltin. Basit tekrar kodunda bu yerel karakterden bir şeyler vardır, ancak onu tahrifata karşı bu kadar savunmasız kılan da tam olarak budur. Bunun aksine, yerel olarak düzeltilebilir bir kod, her iki açıdan da en iyi sonucu verir; Reed-Solomon kodlarını bu kadar dayanıklı kılan birbirine bağlılığı kaybetmeden yalnızca birkaç sorguyla herhangi bir bitteki hatayı düzeltebilir.

Kothari, "Bu gerçekten katı bir kavram" dedi.

Yerel olarak düzeltilebilir kodların en ünlü örnekleri, 1954'te matematikçiler tarafından icat edilen saygın hata düzeltme kodunun versiyonlarıdır. David Müller ve Irving Kamış (aynı zamanda Reed-Solomon kodlarının geliştirilmesine de yardımcı oldu). Reed-Solomon kodları gibi, Reed-Muller kodları da uzun mesajları kodlamak için birçok terimin bir araya getirildiği polinomları kullanır.

Reed-Solomon kodlarında kullanılan polinomlar tek bir değişkeni içerir. xdolayısıyla daha fazla terim eklemenin tek yolu daha yüksek güçler kullanmaktır. x. Bu, yalnızca birçok noktaya bakılarak sabitlenebilecek birçok kıpırdanma içeren bir eğri ile sonuçlanır. Reed-Muller kodları bunun yerine, her terimin birden fazla değişkenin birbiriyle çarpılmasını içerebildiği polinomları kullanır. Daha fazla değişken, bunları birleştirmenin daha fazla yolu anlamına gelir; bu da, herhangi bir bireysel değişkeni bu kadar yüksek güçlere yükseltmeden polinom terimlerinin sayısını artırmanın bir yolunu sunar.

Reed-Muller kodları çok esnektir. Polinomda görünen en yüksek gücü artırarak, değişken sayısını artırarak veya her ikisini birden yaparak daha uzun mesajları kodlayabilirsiniz. Bir Reed-Muller kodunu yerel olarak düzeltilebilir hale getirmek için, her değişkenin maksimum gücünü küçük bir sabit değerle sınırlamanız ve yalnızca değişken sayısını artırarak daha uzun mesajları işlemeniz yeterlidir.

Özellikle üç sorgulu yerel olarak düzeltilebilir bir kod için bu maksimum güç 2'ye ayarlanır. Daha sonra, her bir değişken söz konusu olduğunda, mesajı kodlayan polinom basit bir parabolün izini sürer. Bu parabolün tam şeklini belirlemek için eğriyi yalnızca üç noktada incelemeniz gerekir. Dahası, pek çok değişkenle birlikte, herhangi biri hataları düzeltmek için kullanılabilen bu türden pek çok parabol vardır. Reed-Muller kodlarını bu kadar dayanıklı kılan da budur.

Maalesef Reed-Muller kodunun ciddi bir dezavantajı var: Bir mesajı kodlamak için gereken bit sayısı, değişken sayısıyla birlikte katlanarak artıyor. Yalnızca bir avuç sorguyla hataları düzelten son derece yerel bir kod istiyorsanız, uzun mesajlar için çok sayıda değişkene ihtiyacınız olacak ve Reed-Muller kodu pratikte hızla işe yaramaz hale gelecektir.

Dvir, "Bu durumda üstellik çok kötü" dedi. Ama bu kaçınılmaz mı?

Düzeltilebilir mi, Çözülebilir mi?

Bilgisayar bilimcileri daha verimli yerel olarak düzeltilebilir kodlar bulmaya çalışıp başarısız oldukça, bu tür kodların hiçbir şekilde mümkün olmadığından şüphelenmeye başladılar. 2003 yılında iki araştırmacı kanıtladı Reed-Muller kodunu yalnızca iki sorgu kullanarak aşmanın bir yolu yok. Ama bu herkesin anlayabileceği kadarıyla.

Kothari, "Üçüne gittiğinizde bilgimiz çok yarım yamalak hale geliyor" dedi.

Bir sonraki atılım işleri daha da karmaşık hale getirdi. Yayınlanan iki makalede 2008 ve 2009Bilgisayar bilimcileri Sergey Yekhanin ve Klim Efremenko, Reed-Muller kodlarından daha verimli olan üç sorgulu kodların nasıl oluşturulacağını gösterdiler, ancak bu kodlar yerel olarak tam olarak düzeltilemezdi. Bunun yerine, yerel kod çözülebilirlik adı verilen oldukça farklı bir özelliğe sahiplerdi.

Farkı anlamak için yine kullanıcıların verilerini tek bir uzun mesajda birleştiren ve hata düzeltme kodu kullanarak koruyan bir bulut depolama sağlayıcısı hayal edelim. Hem yerel olarak düzeltilebilen kodlar hem de yerel olarak kodu çözülebilen kodlar, yalnızca birkaç sorguyla orijinal mesajın herhangi bir bitindeki hatayı düzeltebilir.

Ancak her hata düzeltme kodu aynı zamanda orijinal mesajda bulunmayan ekstra bitler de gerektirir; bu nedenle bir mesajın kodlanması onu daha uzun hale getirir. İki kod türü, bu ek bitleri nasıl işledikleri açısından farklılık gösterir. Yerel olarak kodu çözülebilen kodlar, bu bitlerdeki hataları düzeltmek için gereken sorgu sayısı konusunda hiçbir vaatte bulunmaz. Ancak yerel olarak düzeltilebilir bir kodda, ekstra bitlerin herhangi birindeki bir hata, orijinal mesajın herhangi bir bitindeki hatayla tam olarak aynı şekilde düzeltilebilir.

"Kullanıcıların orijinal verileri, yedeklilik ve kontrol bilgileri olsun, sakladığınız her şey yerel olarak düzeltilebilir" dedi Madhu SudanHarvard Üniversitesi'nde bilgisayar bilimcisi.

Prensipte farklı olmasına rağmen, yerel düzeltilebilirlik ve yerel kod çözülebilirlik, 2008'den önce pratikte her zaman birbirinin yerine geçebilir görünüyordu; bilinen her yerel olarak kodu çözülebilir kod, aynı zamanda yerel olarak da düzeltilebilirdi. Yekhanin ve Efremenko'nun keşfi, iki durum arasında temel bir fark olasılığını gündeme getirdi. Ya da belki Yekhanin ve Efremenko'nun kodlarını yerel olarak düzeltilebilir hale getirecek şekilde değiştirmek mümkündü. Bu, iki koşulu bir kez daha eşit zemine oturtacaktır, ancak aynı zamanda araştırmacıların, üç sorgulu yerel olarak düzeltilebilir kodların ne kadar verimli olabileceği konusunda yanıldığı anlamına da gelecektir. Her iki durumda da geleneksel bilgeliğin değişmesi gerekecekti.

Ödünç Alma Mantığı

Kothari ve Manohar nihayet bilgisayar biliminin farklı bir alanından bir tekniği uyarlayarak bu gerilimi çözdüler: Kısıt tatmini sorunlarının incelenmesi. Akşam yemeği planlarını bir arkadaş grubuyla koordine etmeye çalışmak bir tür kısıtlama tatmini sorunudur. Herkesin kabul edeceği seçimleri ve veto edeceği seçimleri vardır. Göreviniz ya herkesi memnun edecek bir plan bulmak, ya da eğer böyle bir plan yoksa bunu bir an önce çözmektir.

Bu iki olası sonuç arasında doğal bir asimetri var. Kabul edilebilir bir çözüm bulmak kolay olmayabilir, ancak bir kez bulduğunuzda, başkalarını bunun işe yarayacağına ikna etmek kolaydır. Ancak sorunun gerçekten "tatmin edilemez" olduğunu bilseniz bile kanıt sağlayacak bir örnek olmayabilir.

2021'de Kothari ve Manohar, Berkeley'deki California Üniversitesi'nden Venkatesan Guruswami ile birlikte bir büyük atılım Bu zor tatmin edilemeyen durumları tanımlamak için yeni bir teorik teknik kullanarak kısıtlama tatmini problemlerinin incelenmesinde. Yeni yöntemin diğer sorunları çözmek için de güçlü bir araç olacağından şüphelendiler ve Guruswami'nin yüksek lisans öğrencisi Omar Alrabiah, yerel olarak kodu çözülebilen üç sorgulu kodlara bakmalarını önerdi.

Kothari, "Bu tabiri caizse elimizde çekiç olan bir çiviydi" dedi.

Yekhanin ve Efremenko'nun şaşırtıcı sonuçları, üç sorgulu yerel olarak kodu çözülebilen kodların Reed-Muller kodlarından daha verimli olabileceğini göstermişti. Peki kodları mümkün olan en iyi kodlar mıydı, yoksa yerel olarak kodu çözülebilen üç sorgulu kodlar daha da verimli hale gelebilir miydi? Kothari, Manohar, Guruswami ve Alrabiah, yeni tekniklerinin bu tür kodların ne kadar verimli olabileceğinin sınırlarını kanıtlayabileceğini düşündüler. Planları, belirli bir boyuttaki tüm olası üç sorgulu yerel olarak kodu çözülebilen kodların yapısını kapsayan mantıksal bir formül oluşturmak ve bunun tatminsiz olduğunu kanıtlamak, böylece böyle bir kodun var olamayacağını göstermekti.

Dört araştırmacı 2022'de bu yönde ilk adımı attı ve yeni sınır üç sorgulu yerel olarak kodu çözülebilen kodların maksimum verimliliği üzerine. Sonuç, araştırmacıların diğer tekniklerle elde edebildiklerinin çok ötesine geçti ancak Yekhanin ve Efremenko'nunkinden daha verimli olan tüm kodları göz ardı etmedi.

Kothari ve Manohar daha ileri gidebileceklerinden şüpheleniyorlardı. Ancak Manohar, tekniğin yerel olarak düzeltilebilir kodlar için yerel olarak kodu çözülebilen kodlardan daha iyi çalışabileceğini gösteren hızlı bir arka plan hesaplaması yazana kadar ilerleme durdu.

Birkaç ay sonra, fazla iyimser olduklarından korkmalarına neden olan birçok yanlış başlangıçtan sonra, teknik nihayet sözünü yerine getirdi. Kothari ve Manohar, araştırmacıların şüphelendiği gibi, yerel olarak düzeltilebilen herhangi bir üç sorgulu kodun Reed-Muller kodlarından kayda değer ölçüde daha iyi çalışmasının imkansız olduğunu kanıtladı. Bu üstel ölçeklendirme temel bir sınırlamadır. Elde ettikleri sonuç, yerel düzeltilebilirlik ile yerel kod çözülebilirliğin, yüzeysel olarak benzer olmasına rağmen, aslında temel düzeyde farklı olduklarının çarpıcı bir göstergesiydi: İkincisinin gerçekleştirilmesi, tartışmasız bir şekilde, ilkinden daha kolaydır.

Kothari ve Manohar artık tekniklerini, üçten fazla sorgu yapılmasına izin verilen kodları inceleyecek şekilde genişletmeyi umuyorlar; zira onlar hakkında şu anda çok az şey biliniyor. Ve hata düzeltme teorisindeki ilerlemenin çoğu zaman görünüşte ilgisiz olan diğer alanlara da etkileri vardır. Özellikle, yerel olarak düzeltilebilir kodlar, her yerde şaşırtıcı bir şekilde ortaya çıkıyor. özel veritabanı aramaları kriptografide kanıtlarına kombinatorik teoremleri. Kothari ve Manohar'ın tekniğinin bu farklı alanları nasıl etkileyeceğini söylemek için henüz çok erken, ancak araştırmacılar iyimser düşünüyor.

Dvir, "Burada gerçekten çok güzel yeni bir fikir var" dedi. "Çok fazla potansiyel olduğunu düşünüyorum."