ثابت شد که طرح تصحیح خطا «جادویی» ذاتاً ناکارآمد است | مجله کوانتا

اگر تا به حال پیام متنی ارسال کرده اید، سی دی پخش کرده اید یا فایلی را در فضای ابری ذخیره کرده اید، از تصحیح خطا بهره مند شده اید. این ایده انقلابی به دهه 1940 برمی گردد، زمانی که محققان برای اولین بار متوجه شدند که می توان هر پیامی را به شکلی بازنویسی کرد که فساد بعدی را به راحتی معکوس کرد.

در طول سال‌ها، محققان طرح‌های مبتکرانه زیادی به نام کدهای تصحیح خطا ایجاد کرده‌اند که داده‌ها را به روش‌های مختلف رمزگذاری می‌کنند و از روش‌های مختلفی برای رفع خطاها استفاده می‌کنند. اما برای دانشمندان نظری کامپیوتر، تعداد کمی به اندازه کدهای به اصطلاح محلی قابل تصحیح قانع کننده هستند. این کدها دو ویژگی همزمان دارند که تقریباً متناقض به نظر می‌رسند: هر خطایی را می‌توان با خواندن داده‌های رمزگذاری‌شده فقط در چند مکان تصحیح کرد، با این حال هیچ مهاجمی نمی‌تواند با دستکاری انتخابی کد، این روش اصلاح را خنثی کند. گویی می توانید هر صفحه ای که از یک کتاب پاره شده است را با نگاه کردن به چند کتاب دیگر بازیابی کنید.

گفت: «این یک پدیده کاملاً جادویی است تام گور، دانشمند کامپیوتر در دانشگاه کمبریج. "پیشینی، واضح نیست که چنین شیء ریاضی اصلا وجود داشته باشد."

اما این جادو هزینه گزافی دارد. تنها نمونه‌های شناخته‌شده کدهای قابل تصحیح محلی بسیار ناکارآمد هستند – رمزگذاری هر پیامی نیز آن را به‌طور تصاعدی طولانی‌تر می‌کند. کل کتاب‌هایی که به این روش کدگذاری شده‌اند، بسیار ناکارآمد خواهند بود.

دانشمندان کامپیوتر مدت‌هاست به این فکر می‌کردند که آیا کدهای قابل اصلاح محلی بهتری امکان‌پذیر است یا خیر. آنها به ویژه بر روی کدهایی تمرکز کرده اند که فقط از سه پرس و جو برای تصحیح هر خطا استفاده می کنند، امیدوارند که این محدودیت شدید ممکن است درک این کدها را آسان تر کند. اما حتی همین مورد ساده بیش از 20 سال است که محققان را سرگردان کرده است.

حالا دانشمند کامپیوتر پروش کوثری از دانشگاه کارنگی ملون و دانشجوی کارشناسی ارشدش پیتر منوهار در نهایت داشته باشند ثابت ساخت یک کد سه پرس و جو به صورت محلی قابل تصحیح غیرممکن است که از این هزینه نمایی جلوگیری کند. ممکن است یک نتیجه منفی باشد، اما هر چیزی که محدودیت‌های تصحیح خطا را روشن کند برای محققان هیجان‌انگیز است، به‌ویژه به این دلیل که ریاضیات کدهای قابل تصحیح محلی در مناطق دور از ارتباط ظاهر می‌شوند.

گفت: این نتیجه شگفت انگیز است شبهنگی صراف، دانشمند کامپیوتر در دانشگاه تورنتو. "این یک پیشرفت بزرگ است."

قدرت در تعداد

برای درک تصحیح خطا، داده‌هایی را که می‌خواهید محافظت کنید به‌عنوان دنباله‌ای از بیت‌ها یا 0 و 1 تصور کنید. یک خطا، در این مدل، می تواند هر چرخش ناخواسته 0 به 1 یا بالعکس باشد، چه به دلیل یک نوسان تصادفی یا دستکاری عمدی باشد.

فرض کنید می خواهید برای دوستی پیامی ارسال کنید، اما نگران هستید که خطاها ممکن است معنی را تغییر دهد. یک استراتژی ساده این است که هر 0 در پیام خود را با 000 و هر 1 را با 111 جایگزین کنید. اگر دوست شما بخشی از پیام را ببیند که شامل سه بیت یکسان در یک ردیف نیست، متوجه می شود که خطایی رخ داده است. و اگر خطاها تصادفی و نسبتاً نادر باشند، هر رشته 110 به احتمال زیاد 111 خراب است تا 000 خراب. رای اکثریت ساده در هر سه گانه برای تصحیح بیشتر خطاها کافی است.

این طرح، که کد تکرار نامیده می شود، دارای فضیلت سادگی است، اما چیز دیگری برای توصیه به آن وجود ندارد. برای یک چیز، نیاز به سه برابر کردن طول هر پیام فقط برای مقابله با خطاهای نسبتاً نادر است، و اگر شانس مناسبی برای دو خطای مجاور وجود داشته باشد، حتی به افزونگی بیشتری نیاز خواهیم داشت. بدتر از آن، اگر خطاها تصادفی نباشند، مانند زمانی که مهاجمان به طور فعال سعی می کنند کد را خراب کنند، به سرعت بی فایده می شود. در کد تکرار، تمام اطلاعات مورد نیاز برای تصحیح یک بیت معین تنها در چند بیت دیگر ذخیره می شود و آن را در برابر یک حمله هدفمند آسیب پذیر می کند.

خوشبختانه، بسیاری از کدهای تصحیح خطا عملکرد بهتری دارند. یک مثال معروف، به نام کد رید-سلیمان، با تبدیل پیام ها به چند جمله ای کار می کند - عبارات ریاضی مانند x² + 3x + 2 که شامل عبارت‌های مختلفی است که به هم اضافه می‌شوند، هر کدام دارای یک متغیر (مانند x) به قدرتی متفاوت ارتقا یافته است. رمزگذاری یک پیام با استفاده از کد رید-سولومون شامل ساختن یک چند جمله ای با یک جمله برای هر کاراکتر در پیام، سپس ترسیم چند جمله ای به عنوان یک منحنی بر روی یک نمودار و ذخیره مختصات نقاطی است که روی منحنی قرار دارند (با گرفتن حداقل یک مورد دیگر). نقطه نسبت به تعداد کاراکترها). خطاها ممکن است تعدادی از این نقاط را از منحنی خارج کنند، اما اگر خطاهای زیادی وجود نداشته باشد، فقط یک منحنی چند جمله ای از بیشتر نقاط عبور می کند. این منحنی تقریباً به طور قطع با پیام واقعی مطابقت دارد.

کدهای Reed-Solomon بسیار کارآمد هستند - برای تصحیح خطاها فقط باید چند امتیاز اضافی ذخیره کنید، بنابراین هر پیام رمزگذاری شده فقط کمی طولانی تر از نسخه اصلی است. آنها همچنین نسبت به نوع اختلال هدفمندی که باعث فاجعه برای کد تکرار می شود کمتر آسیب پذیر هستند، زیرا اطلاعات مورد استفاده برای تصحیح یک خطا در هر جایی در کل پیام رمزگذاری شده توزیع می شود.

فکر می کنم در سطح جهانی، قانون محلی

قدرت کد رید-سولومون از ارتباط متقابل ناشی می شود. اما دقیقاً به دلیل این ارتباط، هیچ راهی برای رفع یک خطا در یک پیام رمزگذاری شده بدون خواندن کامل وجود ندارد. ممکن است در زمینه ارتباط مشکلی به نظر نرسد: اگر در حال ارسال پیام هستید، احتمالاً می خواهید که گیرنده همه آن را بخواند. اما این می تواند یک مسئولیت در ذخیره سازی داده ها باشد - یکی دیگر از کاربردهای اصلی تصحیح خطا.

شرکتی را در نظر بگیرید که ایمیل‌های کاربران را در فضای ابری ذخیره می‌کند – یعنی در مجموعه وسیعی از سرورها. می توانید کل مجموعه ایمیل ها را به عنوان یک پیام طولانی در نظر بگیرید. حال فرض کنید یک سرور از کار بیفتد. با یک کد Reed-Solomon، شما باید یک محاسبات عظیم شامل تمام داده های رمزگذاری شده انجام دهید تا ایمیل های خود را از آن سرور گمشده بازیابی کنید. گفت: "شما باید به همه چیز نگاه کنید." زیو دویر، دانشمند کامپیوتر در دانشگاه پرینستون. "این می تواند میلیاردها و میلیاردها ایمیل باشد - ممکن است زمان زیادی طول بکشد."

محققان از اصطلاح محلی برای توصیف کدهایی استفاده می کنند که تنها بخشی از پیام رمزگذاری شده را به کار می برند. خطاهای نقطه ای یا آنها را اصلاح کنید. کد تکرار ساده چیزی شبیه به این ویژگی محلی دارد، اما این دقیقاً همان چیزی است که آن را در برابر دستکاری آسیب‌پذیر می‌کند. در مقابل، یک کد قابل تصحیح محلی، بهترین‌ها را از هر دو دنیا دریافت می‌کند – می‌تواند یک خطا را در هر لحظه با چند پرس‌وجو تصحیح کند، همگی بدون از دست دادن ارتباط متقابلی که کدهای Reed-Solomon را بسیار انعطاف‌پذیر می‌کند.

کوتری گفت: «این یک تصور واقعاً سختگیرانه است.

معروف‌ترین نمونه‌های کدهای قابل تصحیح محلی، نسخه‌هایی از یک کد اصلاح‌کننده خطای محترم است که در سال 1954 توسط ریاضیدانان اختراع شد. دیوید مولر و ایروینگ رید (که همچنین به توسعه کدهای Reed-Solomon کمک کرد). مانند کدهای Reed-Solomon، کدهای Reed-Muller از چندجمله‌ای استفاده می‌کنند که اصطلاحات زیادی با هم اضافه می‌شوند تا پیام‌های طولانی را رمزگذاری کنند.

چند جمله ای های مورد استفاده در کدهای Reed-Solomon شامل یک متغیر منفرد هستند، x، بنابراین تنها راه برای اضافه کردن اصطلاحات بیشتر استفاده از قدرت های بالاتر است x. این منجر به یک منحنی با تکان‌های بسیار می‌شود که فقط با نگاه کردن به نقاط زیادی می‌توان آن را پین کرد. کدهای Reed-Muller در عوض از چندجمله‌ای استفاده می‌کنند که در آن هر عبارت می‌تواند شامل چندین متغیر باشد که با هم ضرب شده‌اند. متغیرهای بیشتر به معنای راه‌های بیشتری برای ترکیب آنهاست، که به نوبه خود راهی برای افزایش تعداد عبارت‌های چند جمله‌ای بدون افزایش هیچ متغیری به چنین توان بالایی ارائه می‌دهد.

کدهای رید مولر بسیار انعطاف پذیر هستند. می توانید پیام های طولانی تر را با افزایش بالاترین توانی که در چند جمله ای ظاهر می شود، افزایش تعداد متغیرها یا هر دو رمزگذاری کنید. برای اینکه کد Reed-Muller به صورت محلی قابل تصحیح باشد، کافی است حداکثر توان هر متغیر را در یک مقدار ثابت کوچک بپوشانید و تنها با افزایش تعداد متغیرها، پیام‌های طولانی‌تر را مدیریت کنید.

به طور خاص برای یک کد سه پرس و جوی محلی قابل تصحیح، حداکثر توان روی 2 تنظیم می شود. سپس تا آنجا که به هر متغیر جداگانه مربوط می شود، چند جمله ای رمزگذاری کننده پیام یک سهمی ساده را ردیابی می کند. برای تعیین شکل دقیق آن سهمی، فقط باید منحنی را در سه نقطه بررسی کنید. علاوه بر این، با متغیرهای بسیار، چنین سهمی‌های زیادی وجود دارد که از هر کدام می‌توان برای تصحیح خطاها استفاده کرد. این همان چیزی است که کدهای Reed-Muller را بسیار انعطاف پذیر می کند.

متأسفانه کد Reed-Muller یک اشکال جدی دارد: تعداد بیت های مورد نیاز برای رمزگذاری یک پیام به صورت تصاعدی با تعداد متغیرها افزایش می یابد. اگر یک کد بسیار محلی می‌خواهید که خطاها را فقط با تعداد انگشت شماری پرس و جو تصحیح کند، به متغیرهای زیادی برای پیام‌های طولانی نیاز دارید و کد Reed-Muller به سرعت در عمل بی‌فایده می‌شود.

دویر گفت: «تصویری در این مورد بسیار بد است. اما آیا اجتناب ناپذیر است؟

قابل اصلاح یا رمزگشایی؟

از آنجایی که دانشمندان کامپیوتر تلاش کردند و نتوانستند کدهای قابل تصحیح محلی کارآمدتری را بیابند، شروع به شک کردند که چنین کدهایی اصلا امکان پذیر نیست. در سال 2003 دو محقق ثابت که هیچ راهی برای شکست دادن کد Reed-Muller تنها با استفاده از دو کوئری وجود ندارد. اما این تا جایی است که هر کسی به آن رسیده است.

کوتاری گفت: «وقتی به سه می‌روید، دانش ما بسیار واضح می‌شود.

پیشرفت بعدی فقط مسائل را پیچیده تر کرد. در دو مقاله منتشر شده در 2008 و 2009دانشمندان کامپیوتر سرگئی یکانین و کلیم افرمنکو نشان دادند که چگونه می توان کدهای سه پرس و جو ساخت که از کدهای رید مولر کارآمدتر بودند، اما این کدها کاملاً به صورت محلی قابل تصحیح نبودند. در عوض، آنها ویژگی متفاوتی به نام رمزگشایی محلی داشتند.

برای درک تفاوت، بیایید دوباره یک ارائه‌دهنده ذخیره‌سازی ابری را تصور کنیم که داده‌های کاربران را در یک پیام طولانی ترکیب می‌کند و با استفاده از یک کد تصحیح خطا از آن محافظت می‌کند. هم کدهای قابل تصحیح محلی و هم کدهای قابل رمزگشایی محلی می توانند یک خطا را در هر بیت از پیام اصلی تنها با چند پرس و جو تصحیح کنند.

اما هر کد تصحیح خطا به بیت‌های اضافی نیز نیاز دارد که در پیام اصلی نبودند – به همین دلیل است که رمزگذاری یک پیام باعث طولانی‌تر شدن آن می‌شود. دو نوع کد در نحوه برخورد آنها با بیت های اضافی متفاوت است. کدهای قابل رمزگشایی محلی هیچ قولی در مورد تعداد پرس و جوهای مورد نیاز برای تصحیح خطاهای این بیت ها نمی دهند. اما در یک کد قابل تصحیح محلی، یک خطا در هر یک از بیت های اضافی را می توان دقیقاً به همان روشی که خطا در هر بیت از پیام اصلی رفع می شود.

گفت: «هر چیزی که ذخیره می‌کنید، خواه داده‌های اصلی کاربران باشد یا اطلاعات اضافی و چک - همه این‌ها را می‌توان به صورت محلی اصلاح کرد.» مادو سودان، دانشمند کامپیوتر در دانشگاه هاروارد.

اگرچه در اصل متفاوت بود، اما تصحیح پذیری محلی و رمزگشایی محلی همیشه قبل از سال 2008 در عمل قابل تعویض به نظر می رسید - هر کد شناخته شده قابل رمزگشایی محلی نیز به صورت محلی قابل اصلاح بود. کشف یکانین و افرمنکو امکان تفاوت اساسی بین این دو شرط را افزایش داد. یا شاید بتوان کدهای Yekhanin و Efremenko را تغییر داد تا آنها را به صورت محلی اصلاح کرد. این دو شرط را بار دیگر در شرایط مساوی قرار می دهد، اما همچنین به این معنی است که محققان در مورد میزان کارآمدی کدهای سه پرس و جوی محلی قابل اصلاح اشتباه کرده اند. در هر صورت، عقل متعارف باید تغییر کند.

منطق قرض گرفتن

کوتاری و منوهار در نهایت این تنش را با تطبیق تکنیکی از حوزه‌ای متفاوت از علوم رایانه حل کردند: مطالعه مشکلات به اصطلاح رضایت از محدودیت. تلاش برای هماهنگ کردن برنامه های شام با گروهی از دوستان به نوعی مشکل رضایت از محدودیت است. همه انتخاب هایی دارند که می پذیرند و انتخاب هایی که وتو می کنند. وظیفه شما این است که یا طرحی بیابید که همه را راضی کند، یا اگر چنین برنامه ای وجود ندارد، آن را در اسرع وقت مشخص کنید.

یک عدم تقارن ذاتی بین این دو نتیجه احتمالی وجود دارد. یافتن راه حل قابل قبول ممکن است آسان نباشد، اما زمانی که آن را دارید، به راحتی می توانید دیگران را متقاعد کنید که کارساز خواهد بود. اما حتی اگر می‌دانید که مشکل واقعاً «راضی‌ناپذیر» است، ممکن است نمونه‌ای وجود نداشته باشد که اثبات کند.

در سال 2021، کوتاری و منوهار به همراه ونکاتسان گوروسوامی از دانشگاه کالیفرنیا، برکلی، موفقیت بزرگ در مطالعه مشکلات رضایت از محدودیت با استفاده از یک تکنیک نظری جدید برای شناسایی آن موارد غیرقابل ارضای مشکل. آنها مشکوک بودند که روش جدید ابزار قدرتمندی برای حل مشکلات دیگر نیز خواهد بود، و عمر الربیا، دانشجوی فارغ التحصیل گوروسوامی، به آنها پیشنهاد کرد که کدهای سه پرس و جوی محلی قابل رمزگشایی را بررسی کنند.

کوثری گفت: «این یک میخ با چکش در دست ما بود.

نتایج شگفت‌انگیز یکانین و افرمنکو نشان داده بود که کدهای سه پرس و جوی قابل رمزگشایی محلی می‌توانند کارآمدتر از کدهای Reed-Muller باشند. اما آیا کدهای آنها بهترین کدهای ممکن بود یا اینکه کدهای سه پرس و جوی محلی قابل رمزگشایی حتی کارآمدتر بودند؟ Kothari، Manohar، Guruswami و Alrabiah فکر می‌کردند که تکنیک جدید آنها ممکن است بتواند محدودیت‌هایی را در مورد میزان کارآمدی چنین کدهایی ثابت کند. برنامه آنها این بود که یک فرمول منطقی بسازند که ساختار همه کدهای سه پرس و جوی ممکن را به صورت محلی رمزگشایی با یک اندازه معین در بر بگیرد و ثابت کنند که قابل قبول نیست و در نتیجه نشان دهند که چنین کدی نمی تواند وجود داشته باشد.

این چهار محقق اولین گام را در این مسیر در سال 2022 برداشتند و یک محدودیت جدید بر روی حداکثر کارایی کدهای سه پرس و جوی قابل رمزگشایی محلی. نتیجه بسیار فراتر از آن چیزی بود که محققان توانسته بودند با تکنیک های دیگر به دست آورند، اما همه کدهای کارآمدتر از یکانین و افرمنکو را رد نکرد.

کوتاری و منوهار مشکوک بودند که می‌توانند جلوتر بروند. اما پیشرفت متوقف شد تا اینکه Manohar یک محاسبه سریع پشت پاکت را یادداشت کرد که نشان می‌دهد این تکنیک ممکن است برای کدهای قابل اصلاح محلی حتی بهتر از کدهای قابل رمزگشایی محلی کار کند.

چند ماه بعد، پس از شروع های نادرست بسیاری که باعث ترس آنها از خوش بین بودن آنها شد، این تکنیک سرانجام به وعده خود عمل کرد. Kothari و Manohar ثابت کردند که همانطور که محققان گمان می‌کردند، غیرممکن است که هر کد سه پرس و جوی محلی قابل تصحیح بهتر از کدهای Reed-Muller کار کند. این مقیاس نمایی یک محدودیت اساسی است. نتیجه آنها همچنین نشان دادن چشمگیر این بود که تصحیح پذیری محلی و رمزگشایی محلی، اگرچه ظاهراً مشابه هستند، اما واقعاً در سطح اساسی متفاوت هستند: درک دومی به وضوح آسان تر از اولی است.

Kothari و Manohar اکنون امیدوارند تکنیک های خود را به مطالعه کدهایی بسط دهند که مجاز به انجام بیش از سه پرس و جو هستند، زیرا در حال حاضر اطلاعات کمی در مورد آنها وجود دارد. و پیشرفت در تئوری تصحیح خطا اغلب پیامدهایی در زمینه های به ظاهر نامرتبط دیگر دارد. به طور خاص، کدهای قابل تصحیح محلی در همه جا به دلیل مشکل از ظاهر شگفت‌انگیز می‌شوند جستجو در پایگاه داده خصوصی در رمزنگاری به اثبات قضایا در ترکیبات. هنوز خیلی زود است که بگوییم تکنیک کوتاری و منوهار چه تأثیری بر این زمینه‌های مختلف خواهد گذاشت، اما محققان خوش‌بین هستند.

دویر گفت: «یک ایده جدید بسیار زیبا در اینجا وجود دارد. "من فکر می کنم پتانسیل زیادی وجود دارد."