Tornado code
کوڈنگ تھیوری میں، ٹورنیڈو کوڈز مٹانے والے کوڈز کی ایک کلاس ہیں جو غلطی کی اصلاح کی حمایت کرتے ہیں۔ ٹورنیڈو کوڈز کے لیے زیادہ ڈیٹا ایفیشنٹ ریڈ سولومن ایرزر کوڈز کے مقابلے میں مستقل سی زیادہ بے کار بلاکس کی ضرورت ہوتی ہے، لیکن یہ پیدا کرنے میں بہت تیز ہوتے ہیں اور ایرزرز کو تیزی سے ٹھیک کر سکتے ہیں۔ ٹورنیڈو کوڈز کے سافٹ ویئر پر مبنی نفاذ چھوٹی لمبائی پر تقریبا 100 گنا تیز اور ریڈ سولومن ایرزر کوڈز سے بڑی لمبائی پر تقریبا 10,000 گنا تیز ہوتے ہیں۔ ٹورنیڈو کوڈز کے تعارف کے بعد سے، اسی طرح کے بہت سے دوسرے مٹانے والے کوڈز ابھر کر سامنے آئے ہیں، خاص طور پر آن لائن کوڈز، ایل ٹی کوڈز اور ریپٹر کوڈز۔ ٹورنیڈو کوڈز پرتوں والے نقطہ نظر کا استعمال کرتے ہیں۔ آخری استعمال ایل ڈی پی سی ایرر کریکشن کوڈ کے علاوہ تمام پرتیں، جو تیز ہے لیکن اس میں ناکامی کا امکان ہے۔ آخری پرت ریڈ سولومن اصلاح کوڈ کا استعمال کرتی ہے، جو سست ہے لیکن ناکامی کی بازیابی کے لحاظ سے بہترین ہے۔ ٹورنیڈو کوڈز یہ طے کرتے ہیں کہ کتنی سطحیں، ہر سطح میں کتنے ریکوری بلاکس، اور غیر حتمی تہوں کے لیے بلاکس پیدا کرنے کے لیے استعمال ہونے والی تقسیم۔ جائزہ ان پٹ ڈیٹا کو بلاکس میں تقسیم کیا گیا ہے۔ بلاکس بٹس کے سلسلے ہیں جو ایک ہی سائز کے ہوتے ہیں۔ ریکوری ڈیٹا اسی بلاک سائز کا استعمال کرتا ہے جو ان پٹ ڈیٹا کرتا ہے۔ بلاک (ان پٹ یا ریکوری) کے مٹ جانے کا پتہ کسی اور طریقے سے لگایا جاتا ہے۔ (مثال کے طور پر، ڈسک سے ایک بلاک سی آر سی چیک کو پاس نہیں کرتا ہے یا ایک نیٹ ورک پیکٹ جس میں دی گئی ترتیب نمبر کبھی نہیں آتا ہے۔) بازیابی کے بلاکس کی تعداد صارف کی طرف سے دی جاتی ہے۔ پھر ہر سطح میں بلاکس کی تعداد کے ساتھ سطحوں کی تعداد کا تعین کیا جاتا ہے۔ ہر سطح میں تعداد کا تعین ایک عنصر B سے ہوتا ہے جو ایک سے کم ہے۔ اگر N ان پٹ بلاکس ہیں، تو پہلی بازیابی کی سطح میں B * N بلاکس ہیں، دوسرے میں B * B * N ہے، تیسرے میں B * B * B * N ہے، اور اسی طرح۔ بازیابی کی تمام سطحیں سوائے آخری کے ایل ڈی پی سی کا استعمال کرتی ہیں، جو xor (exclusive-or) کے ذریعے کام کرتی ہے۔ Xor بائنری اقدار، 1s اور 0s پر کام کرتا ہے۔ A xor B 1 ہے اگر A اور B کی اقدار مختلف ہوں اور 0 اگر A اور B کی اقدار ایک جیسی ہوں۔ اگر آپ کو (A xor B) اور A کا نتیجہ دیا جاتا ہے، تو آپ B کی قیمت کا تعین کر سکتے ہیں۔ (A xor B xor A = B) اسی طرح، اگر آپ کو (A xor B) اور B کا نتیجہ دیا جائے، تو آپ A کی قیمت کا تعین کر سکتے ہیں۔ یہ متعدد اقدار تک پھیلا ہوا ہے، لہذا (A xor B xor C xor D) اور کسی بھی 3 اقدار کے نتیجے میں، گمشدہ قیمت کو بازیافت کیا جا سکتا ہے۔ تو سطح ایک میں بازیابی کے بلاکس صرف ان پٹ بلاکس کے کچھ سیٹ کے xor ہیں۔ اسی طرح، سطح دو میں بازیابی کے بلاکس ہر ایک سطح ایک میں بلاکس کے کچھ سیٹ کے xor ہیں۔ xor میں استعمال ہونے والے بلاکس کو بغیر تکرار کے تصادفی طور پر منتخب کیا جاتا ہے۔ تاہم، ریکوری بلاک بنانے کے لیے مختص کردہ بلاکس کی تعداد کا انتخاب ہر سطح کے لیے ایک بہت ہی مخصوص تقسیم سے کیا جاتا ہے۔ چونکہ xor ایک تیز عمل ہے اور بازیابی کے بلاکس ان پٹ (یا کم بازیابی کی سطح پر) میں موجود بلاکس کے صرف ایک ذیلی سیٹ کے xor ہوتے ہیں، اس لیے بازیابی کے بلاکس تیزی سے تیار کیے جا سکتے ہیں۔ آخری سطح ریڈ سولومن کوڈ ہے۔ ریڈ سولومن کوڈز ناکامیوں سے بحالی کے لحاظ سے بہترین ہیں، لیکن پیدا کرنے اور بازیافت کرنے میں سست ہیں۔ چونکہ ہر سطح میں پہلے کے مقابلے میں کم بلاکس ہوتے ہیں، ریڈ سولومن کوڈ میں بازیابی کے بلاکس کی ایک چھوٹی سی تعداد ہوتی ہے جو بازیابی میں پیدا کرنے اور استعمال کرنے کے لیے ہوتی ہے۔ لہذا، اگرچہ ریڈ سولومن سست ہے، اس کے پاس ہینڈل کرنے کے لیے صرف تھوڑی مقدار میں ڈیٹا ہے۔ بازیابی کے دوران، ریڈ سولومن کوڈ پہلے بازیافت کیا جاتا ہے۔ اگر اگلی سے آخری سطح میں گمشدہ بلاکس کی تعداد حتمی سطح میں موجودہ بلاکس سے کم ہے تو یہ کام کرنے کی ضمانت دیتا ہے۔ نیچے جاتے ہوئے، ایل ڈی پی سی (xor) بازیابی کی سطح کو اعلی امکان کے ساتھ اس کے نیچے کی سطح کو بازیافت کرنے کے لیے استعمال کیا جا سکتا ہے اگر تمام بازیابی کے بلاکس موجود ہوں اور نیچے کی سطح بازیابی کی سطح سے زیادہ سے زیادہ C 'کم بلاکس پر غائب ہو۔ بازیابی کے لیے الگورتھم کچھ بازیابی بلاک تلاش کرنا ہے جس میں اس کا صرف ایک جنریٹنگ سیٹ نچلی سطح سے غائب ہے۔ پھر موجود تمام بلاکس کے ساتھ ریکوری بلاک کا xor مسنگ بلاک کے برابر ہوتا ہے۔ پیٹنٹ کے مسائل ٹورنیڈو کوڈز پہلے ریاستہائے متحدہ امریکہ کے اندر پیٹنٹ کیے گئے تھے۔ پیٹنٹ یو ایس 6163870 اے (6 نومبر 1997 کو دائر) اور یو ایس 6081909 اے (6 نومبر 1997 کو دائر) ٹورنیڈو کوڈز کی وضاحت کرتے ہیں، اور 6 نومبر 2017 تک ان کی میعاد ختم ہو چکی ہے۔ پیٹنٹ US6307487 B1 (5 فروری 1999 کو دائر) اور US6320520 B1 (17 ستمبر 1999 کو دائر) میں بھی ٹورنیڈو کوڈز کا ذکر ہے، اور ان کی میعاد بالترتیب 5 فروری 2019 اور 17 ستمبر 2019 تک ختم ہو چکی ہے۔ حوالہ جات مائیکل لوبی نے ٹورنیڈو کوڈز بنائے۔ بیرونی روابط CMU (پوسٹ اسکرپٹ) سے ایک قابل پڑھنے تفصیل اور انٹرنیشنل کمپیوٹر سائنس انسٹی ٹیوٹ (پوسٹ اسکرپٹ) میں لوبی سے ایک اور تفصیل۔ یہ بھی دیکھیں کہ ریپٹر کوڈ مٹانے کا کوڈ نوٹ حوالہ جات کوڈنگ تھیوری صلاحیت کے قریب کوڈز