Viterbi decoder
وٹربی ڈیکوڈر بٹ اسٹریم کو ڈی کوڈ کرنے کے لیے وٹربی الگورتھم کا استعمال کرتا ہے جسے کنولوشنل کوڈ یا ٹریلس کوڈ کا استعمال کرتے ہوئے انکوڈ کیا گیا ہے۔ کنولوشنلی انکوڈڈ اسٹریم کو ڈی کوڈ کرنے کے لیے دیگر الگورتھم بھی ہیں (مثال کے طور پر، فینو الگورتھم)۔ وٹربی الگورتھم سب سے زیادہ وسائل استعمال کرنے والا ہے، لیکن یہ زیادہ سے زیادہ امکان کو ڈیکوڈنگ کرتا ہے۔ یہ اکثر رکاوٹ کی لمبائی k ≤ 3 کے ساتھ کنولوشنل کوڈز کو ڈی کوڈ کرنے کے لیے استعمال ہوتا ہے، لیکن k = 15 تک کی اقدار عملی طور پر استعمال ہوتی ہیں۔ وٹربی ڈیکوڈنگ کو اینڈریو جے وٹربی نے تیار کیا تھا اور کاغذ میں شائع کیا گیا تھا۔ وٹربی ڈیکوڈر کے ہارڈ ویئر (موڈیم میں) اور سافٹ ویئر کے نفاذ دونوں موجود ہیں۔ وٹربی ڈیکوڈنگ کا استعمال تکراری وٹربی ڈیکوڈنگ الگورتھم میں کیا جاتا ہے۔ ہارڈ ویئر کا نفاذ بنیادی (پنکچر نہیں) کوڈ کے لیے ایک ہارڈ ویئر وٹربی ڈیکوڈر عام طور پر مندرجہ ذیل بڑے بلاکس پر مشتمل ہوتا ہے: برانچ میٹرک یونٹ (بی ایم یو) پاتھ میٹرک یونٹ (پی ایم یو) ٹریس بیک یونٹ (ٹی بی یو) برانچ میٹرک یونٹ (بی ایم یو) ایک برانچ میٹرک یونٹ کا کام برانچ میٹرکس کا حساب لگانا ہے، جو کوڈ حروف تہجی میں ہر ممکنہ علامت اور موصولہ علامت کے درمیان معیاری فاصلے ہیں۔ سخت فیصلہ اور نرم فیصلہ وٹربی ڈیکوڈر ہوتے ہیں۔ ایک سخت فیصلہ وٹربی ڈیکوڈر اپنے ان پٹ پر ایک سادہ بٹ اسٹریم وصول کرتا ہے، اور ہیمنگ فاصلہ میٹرک کے طور پر استعمال ہوتا ہے۔ ایک نرم فیصلہ وٹربی ڈیکوڈر ایک بٹ اسٹریم وصول کرتا ہے جس میں ہر موصول شدہ علامت کی وشوسنییتا کے بارے میں معلومات ہوتی ہیں۔ مثال کے طور پر، 3 بٹ انکوڈنگ میں، اس وشوسنییتا کی معلومات کو مندرجہ ذیل طریقے سے انکوڈ کیا جا سکتا ہے: یقینا، وشوسنییتا کے ڈیٹا کو انکوڈ کرنے کا یہ واحد طریقہ نہیں ہے۔ مربع یوکلڈین فاصلہ نرم فیصلہ ڈیکوڈرز کے لیے میٹرک کے طور پر استعمال ہوتا ہے۔ پاتھ میٹرک یونٹ (پی ایم یو) ایک پاتھ میٹرک یونٹ راستوں کے لیے میٹرکس حاصل کرنے کے لیے برانچ میٹرکس کا خلاصہ پیش کرتا ہے، جہاں K کوڈ کی رکاوٹ لمبائی ہے، جن میں سے ایک کو بالآخر بہترین کے طور پر منتخب کیا جا سکتا ہے۔ ہر گھڑی یہ فیصلے کرتی ہے، جان بوجھ کر غیر بہتر راستوں کو پھینک دیتی ہے۔ ان فیصلوں کے نتائج ایک ٹریس بیک یونٹ کی یاد میں لکھے جاتے ہیں۔ پی ایم یو کے بنیادی عناصر اے سی ایس (ایڈ-کمپیر-سلیکٹ) یونٹس ہیں۔ جس طرح سے وہ آپس میں جڑے ہوئے ہیں اس کی وضاحت ایک مخصوص کوڈ کے ٹریلس خاکہ سے کی جاتی ہے۔ چونکہ برانچ میٹرکس ہمیشہ ہوتے ہیں، اس لیے میٹرک کاؤنٹرز کو اوور فلو سے روکنے کے لیے ایک اضافی سرکٹ (تصویر پر نہیں دکھایا گیا) ہونا چاہیے۔ ایک متبادل طریقہ جو راستے کی میٹرک نمو کی نگرانی کرنے کی ضرورت کو ختم کرتا ہے وہ یہ ہے کہ راستے کے میٹرکس کو "رول اوور" کرنے کی اجازت دی جائے۔ اس طریقہ کو استعمال کرنے کے لیے یہ یقینی بنانا ضروری ہے کہ راستے کے میٹرک جمع کرنے والوں میں کافی بٹس موجود ہوں تاکہ "بہترین" اور "بدترین" اقدار کو ایک دوسرے کے 2 (n-1) کے اندر آنے سے روکا جا سکے۔ موازنہ سرکٹ بنیادی طور پر غیر تبدیل شدہ ہے۔ "بہترین" پاتھ میٹرک کی ترقی کی شرح کی نگرانی کرکے آنے والے بٹ اسٹریم پر شور کی سطح کی نگرانی کرنا ممکن ہے۔ ایسا کرنے کا ایک آسان طریقہ یہ ہے کہ کسی ایک مقام یا "ریاست" کی نگرانی کی جائے اور اسے جمع کرنے والے کی حد کے اندر چار مجرد سطحوں سے "اوپر کی طرف" گزرتے ہوئے دیکھا جائے۔ جیسے جیسے یہ ان میں سے ہر ایک حد سے اوپر کی طرف گزرتا ہے، ایک کاؤنٹر میں اضافہ ہوتا ہے جو آنے والے سگنل پر موجود "شور" کی عکاسی کرتا ہے۔ ٹریس بیک یونٹ (ٹی بی یو) بیک ٹریس یونٹ پی ایم یو کے ذریعے لیے گئے فیصلوں سے (تقریبا) زیادہ سے زیادہ روزی روٹی کے راستے کو بحال کرتا ہے۔ چونکہ یہ اسے الٹی سمت میں کرتا ہے، ایک وٹربی ڈیکوڈر ایک درست ترتیب کی تشکیل نو کے لیے ایک FILO (فرسٹ ان لاسٹ آؤٹ) بفر پر مشتمل ہوتا ہے۔ نوٹ کریں کہ تصویر پر دکھائے گئے نفاذ کے لیے دوگنا تعدد درکار ہے۔ کچھ حربے ہیں جو اس ضرورت کو ختم کرتے ہیں۔ نفاذ کے مسائل سافٹ ڈیسیشن ڈیکوڈنگ کے لیے کوانٹائزیشن سافٹ ڈیسیشن ڈیکوڈنگ کے فوائد کو مکمل طور پر بروئے کار لانے کے لیے، کسی کو ان پٹ سگنل کو مناسب طریقے سے کوانٹائز کرنے کی ضرورت ہے۔ زیادہ سے زیادہ کوانٹائزیشن زون کی چوڑائی کی وضاحت مندرجہ ذیل فارمولے سے کی جاتی ہے: جہاں شور پاور سپیکٹرم ڈینسٹی ہے، اور k سافٹ فیصلہ کے لیے بٹس کی ایک تعداد ہے۔ یوکلیڈین میٹرک کمپیوٹیشن کوڈ حروف تہجی میں موصولہ اور اصل علامتوں کے درمیان مربع معیار () کے فاصلے کو لکیری رقم/فرق کی شکل میں مزید آسان بنایا جا سکتا ہے، جو اسے کمپیوٹیشنل طور پر کم گہرا بناتا ہے۔ 1/2 کنولوشنل کوڈ پر غور کریں، جو ہر ان پٹ بٹ (1 یا 0) کے لیے 2 بٹس (00، 01، 10 یا 11) پیدا کرتا ہے۔ ان ریٹرن ٹو زیرو سگنلز کا ساتھ میں دکھائی گئی نان ریٹرن ٹو زیرو شکل میں ترجمہ کیا جاتا ہے۔ ہر موصولہ علامت کو ویکٹر کی شکل میں vr = {r0, r1} کے طور پر پیش کیا جا سکتا ہے، جہاں r0 اور r1 نرم فیصلہ اقدار ہیں، جن کے طول و عرض موصول شدہ ویکٹر، vr کی مشترکہ وشوسنییتا کی نشاندہی کرتے ہیں۔ کوڈ حروف تہجی میں ہر علامت، اسی طرح، ویکٹر vi = {±1, ±1} کی طرف سے نمائندگی کی جا سکتی ہے. یوکلیڈین فاصلہ میٹرک کا اصل حساب یہ ہے: ہر مربع اصطلاح ایک معیاری فاصلہ ہے، جو علامت کی توانائی کو ظاہر کرتا ہے۔ مثال کے طور پر، علامت vi = {± 1, ± 1} کی توانایٔی کا حساب اس طرح لگایا جا سکتا ہے کہ کوڈ حروف تہجی میں تمام علامتوں کی توانایٔی اصطلاح مستقل ((عام کردہ) قدر 2 پر) ہوتی ہے۔ ایڈ-کمپیر-سلیکٹ (ACS) آپریشن موصولہ علامت | |vr | | اور کوڈ حروف تہجی میں کسی بھی 2 علامتوں کے درمیان میٹرک فاصلے کا موازنہ کرتا ہے جس کے راستے متعلقہ ٹریلس میں نوڈ پر ضم ہو جاتے ہیں، | |vi (0) | اور | |vi (1) |۔ لیکن، اوپر سے ہم جانتے ہیں کہ vi کی توانایٔی مستقل (2 کی (معمول شدہ) قدر کے برابر) ہے، اور دونوں صورتوں میں vr کی توانایٔی یکساں ہے۔ اس سے 2 (درمیانی) ڈاٹ پروڈکٹ اصطلاحات کے درمیان منیما فنکشن سے موازنہ کم ہو جاتا ہے، کیونکہ منفی نمبروں پر عمل کو مثبت مقداروں پر مساوی عمل کے طور پر سمجھا جا سکتا ہے۔ ہر ڈاٹ پروڈکٹ کی اصطلاح کو اس طرح بڑھایا جا سکتا ہے جہاں ہر اصطلاح کی علامات کا موازنہ علامتوں، vi (0) اور vi (1) پر ہوتا ہے۔ اس طرح، برانچ میٹرک کا حساب لگانے کے لیے مربع شدہ یوکلڈین میٹرک فاصلے کا حساب ایک سادہ ایڈ/سبٹریکٹ آپریشن کے ساتھ کیا جا سکتا ہے۔ ٹریس بیک کا عمومی نقطہ نظر یہ ہے کہ رکاوٹوں کی لمبائی (5 (K-1)) سے پانچ گنا تک راستے کے میٹرکس کو جمع کیا جائے، سب سے زیادہ جمع شدہ لاگت والے نوڈ کو تلاش کیا جائے، اور اس نوڈ سے ٹریس بیک شروع کیا جائے۔ عام طور پر استعمال ہونے والا انگوٹھے کا قاعدہ جو کہ کنولیوشنل کوڈ کی میموری (رکاوٹ کی لمبائی K-1) سے پانچ گنا زیادہ کٹوتی کی گہرائی کا ہے، صرف ریٹ 1/2 کوڈز کے لیے درست ہے۔ صوابدیدی شرح کے لیے، انگوٹھے کا ایک درست قاعدہ 2.5 (K-1)/(1-r) ہے جہاں r کوڈ کی شرح ہے۔ تاہم، نوڈ کی کمپیوٹنگ جس نے سب سے بڑی لاگت (یا تو سب سے بڑا یا سب سے چھوٹا انٹیگرل پاتھ میٹرک) جمع کی ہے اس میں کئی (عام طور پر 2K-1) نمبروں کا زیادہ سے زیادہ یا کم سے کم تلاش کرنا شامل ہے، جو سرایت شدہ ہارڈ ویئر سسٹمز پر لاگو ہونے پر وقت طلب ہو سکتا ہے۔ زیادہ تر مواصلاتی نظام وٹربی ڈیکوڈنگ کا استعمال کرتے ہیں جس میں مقررہ سائز کے ڈیٹا پیکٹ شامل ہوتے ہیں، جس میں ڈیٹا پیکٹ کے شروع میں یا/اور آخر میں ایک مقررہ بٹ/بائٹ پیٹرن ہوتا ہے۔ معروف بٹ/بائٹ پیٹرن کو حوالہ کے طور پر استعمال کرنے سے، اسٹارٹ نوڈ کو ایک مقررہ قیمت پر سیٹ کیا جا سکتا ہے، جس سے ٹریس بیک کے دوران ایک بہترین زیادہ سے زیادہ امکانات کا راستہ حاصل ہوتا ہے۔ حدود وٹربی ڈیکوڈر کے فزیکل نفاذ سے ان پٹ سگنل، برانچ اور پاتھ میٹرکس، اور محدود ٹریس بیک لمبائی کی مقدار کی وجہ سے درست زیادہ سے زیادہ روزگار کا سلسلہ حاصل نہیں ہوگا۔ عملی نفاذ آئیڈیل کے 1 ڈی بی کے اندر پہنچتے ہیں۔ وٹربی ڈیکوڈر کی آؤٹ پٹ، جب کسی اضافی گوسی چینل سے خراب ہونے والے پیغام کو ڈی کوڈ کرتی ہے، تو اس میں غلطیوں کو ایرر برسٹ میں گروپ کیا جاتا ہے۔ سنگل ایرر کریکٹنگ کوڈز اکیلے اس طرح کے پھٹ کو درست نہیں کر سکتے ہیں، لہذا یا تو کنولوشنل کوڈ اور وٹربی ڈیکوڈر کو اتنا طاقتور ڈیزائن کیا جانا چاہیے کہ غلطیوں کو قابل قبول شرح تک پہنچایا جا سکے، یا برسٹ ایرر کریکٹنگ کوڈز کا استعمال کیا جانا چاہیے۔ پنکچرڈ کوڈز پنکچرڈ کوڈز کا ایک ہارڈ ویئر وٹربی ڈیکوڈر عام طور پر اس طرح سے لاگو کیا جاتا ہے: ایک ڈیپنکچرر، جو ان پٹ اسٹریم کو اسٹریم میں تبدیل کرتا ہے جو ان جگہوں پر ERASE کے نشانات کے ساتھ ایک اصل (غیر پنکچرڈ) اسٹریم کی طرح لگتا ہے جہاں بٹس کو مٹایا گیا تھا۔ ان ERASE نشانات کو سمجھنے والا ایک بنیادی وٹربی ڈیکوڈر (یعنی، انہیں برانچ میٹرک حساب کے لیے استعمال نہیں کرنا)۔ سافٹ ویئر کا نفاذ سب سے زیادہ وقت طلب کارروائیوں میں سے ایک اے سی ایس بٹر فلائی ہے، جسے عام طور پر ڈیکوڈنگ کے وقت کو تیز کرنے کے لیے اسمبلی زبان اور مناسب انسٹرکشن سیٹ ایکسٹینشنز (جیسے ایس ایس ای 2) کا استعمال کرتے ہوئے لاگو کیا جاتا ہے۔ ویٹربی ڈیکوڈنگ الگورتھم مندرجہ ذیل شعبوں میں بڑے پیمانے پر استعمال ہوتا ہے: ریڈیو مواصلات: ڈیجیٹل ٹی وی (اے ٹی ایس سی، کیو اے ایم، ڈی وی بی-ٹی، وغیرہ۔ )، ریڈیو ریلے، سیٹلائٹ مواصلات، شوقیہ ریڈیو کے لیے پی ایس کے 31 ڈیجیٹل موڈ۔ ڈیکوڈنگ ٹریلس کوڈڈ ماڈیولیشن (ٹی سی ایم)، 3 کلو ہرٹز بینڈوڈتھ اینالاگ ٹیلی فون لائنوں میں سے اعلی سپیکٹرم کی کارکردگی کو نچوڑنے کے لیے ٹیلی فون لائن موڈیم میں استعمال ہونے والی تکنیک۔ کمپیوٹر اسٹوریج ڈیوائسز جیسے ہارڈ ڈسک ڈرائیوز۔ خودکار تقریر کی شناخت حوالہ جات بیرونی لنکس وٹربی ڈیکوڈنگ کے ساتھ ساتھ کتابچہ کی تفصیلات۔ ہارڈ ویئر کے نفاذ کے مسائل پر توجہ مرکوز کرتے ہوئے وٹربی الگورتھم کی وضاحت۔ r = 1/6 k = 15 سیٹرن کے لیے کیسینی مشن کے لیے کوڈنگ۔ بہتر سافٹ ویئر کا آن لائن جنریٹر وٹربی ڈیکوڈرز (جی پی ایل)۔ چار معیاری کوڈز کے لیے جی پی ایل وائٹربی ڈیکوڈر سافٹ ویئر۔ کے = 24 وٹربی ڈیکوڈر کی تفصیل، جو کہ عملی استعمال میں اب تک کا سب سے بڑا سمجھا جاتا ہے۔ عام وٹربی ڈیکوڈر ہارڈ ویئر (جی پی ایل)۔ ڈیٹا ٹرانسمیشن میں خرابی کا پتہ لگانے اور اصلاح اعلی اہمیت کے مضامین