Viterbi decoder
একটি ভিটারবি ডিকোডার একটি বিটস্ট্রিম ডিকোড করার জন্য ভিটারবি অ্যালগরিদম ব্যবহার করে যা একটি কনভোলিউশনাল কোড বা ট্রেলিস কোড ব্যবহার করে এনকোড করা হয়েছে। একটি কনভোলিউশনালি এনকোডেড স্ট্রিম ডিকোড করার জন্য অন্যান্য অ্যালগরিদম রয়েছে (উদাহরণস্বরূপ, ফ্যানো অ্যালগরিদম)। ভিটারবি অ্যালগরিদম সর্বাধিক সম্পদ-গ্রহণকারী, তবে এটি সর্বাধিক সম্ভাব্যতা ডিকোডিং করে। এটি প্রায়শই সীমাবদ্ধ দৈর্ঘ্য k ≤ 3 সহ কনভোলিউশনাল কোডগুলি ডিকোডিং করার জন্য ব্যবহৃত হয়, তবে k = 15 পর্যন্ত মানগুলি অনুশীলনে ব্যবহৃত হয়। ভিটারবি ডিকোডিং অ্যান্ড্রু জে ভিটারবি দ্বারা তৈরি করা হয়েছিল এবং গবেষণাপত্রে প্রকাশিত হয়েছিল একটি ভিটারবি ডিকোডারের হার্ডওয়্যার (মডেমে) এবং সফ্টওয়্যার বাস্তবায়ন উভয়ই রয়েছে। ভিটারবি ডিকোডিং পুনরাবৃত্তিমূলক ভিটারবি ডিকোডিং অ্যালগরিদমে ব্যবহৃত হয়। হার্ডওয়্যার বাস্তবায়ন মৌলিক (ছিদ্রযুক্ত নয়) কোডের জন্য একটি হার্ডওয়্যার ভিটারবি ডিকোডার সাধারণত নিম্নলিখিত প্রধান ব্লকগুলি নিয়ে গঠিতঃ শাখা মেট্রিক ইউনিট (বিএমইউ) পাথ মেট্রিক ইউনিট (পিএমইউ) ট্রেসব্যাক ইউনিট (টিবিইউ) শাখা মেট্রিক ইউনিট (বিএমইউ) একটি শাখা মেট্রিক ইউনিটের কাজ হল শাখা মেট্রিক গণনা করা, যা কোড বর্ণমালার প্রতিটি সম্ভাব্য প্রতীক এবং প্রাপ্ত প্রতীকের মধ্যে আদর্শ দূরত্ব। কঠিন সিদ্ধান্ত এবং নরম সিদ্ধান্ত ভিটারবি ডিকোডার রয়েছে। একটি হার্ড ডিসিশন ভিটারবি ডিকোডার তার ইনপুটের উপর একটি সহজ বিটস্ট্রিম গ্রহণ করে এবং একটি হ্যামিং দূরত্ব মেট্রিক হিসাবে ব্যবহৃত হয়। একটি নরম সিদ্ধান্ত ভিটারবি ডিকোডার প্রতিটি প্রাপ্ত প্রতীকের নির্ভরযোগ্যতা সম্পর্কে তথ্য সম্বলিত একটি বিটস্ট্রিম গ্রহণ করে। উদাহরণস্বরূপ, একটি 3-বিট এনকোডিংয়ে, এই নির্ভরযোগ্যতার তথ্য নিম্নরূপ এনকোড করা যেতে পারেঃ অবশ্যই, নির্ভরযোগ্যতার তথ্য এনকোড করার একমাত্র উপায় এটি নয়। বর্গ ইউক্লিডীয় দূরত্ব নরম সিদ্ধান্ত ডিকোডারের জন্য মেট্রিক হিসাবে ব্যবহৃত হয়। পাথ মেট্রিক ইউনিট (পিএমইউ) একটি পাথ মেট্রিক ইউনিট পথের জন্য মেট্রিক্স পেতে শাখা মেট্রিক্সের সংক্ষিপ্তসার দেয়, যেখানে কে কোডের সীমাবদ্ধ দৈর্ঘ্য, যার মধ্যে একটি শেষ পর্যন্ত সর্বোত্তম হিসাবে বেছে নেওয়া যেতে পারে। প্রতিটি ঘড়িতে এটি সিদ্ধান্ত নেয়, ইচ্ছাকৃতভাবে অপ্টিমাল পথগুলি ছুঁড়ে দেয়। এই সিদ্ধান্তগুলির ফলাফল একটি ট্রেসব্যাক ইউনিটের স্মৃতিতে লেখা হয়। একটি পিএমইউ-এর মূল উপাদানগুলি হল এসিএস (অ্যাড-কম্পেয়ার-সিলেক্ট) ইউনিট। যে পদ্ধতিতে তারা নিজেদের মধ্যে সংযুক্ত থাকে তা একটি নির্দিষ্ট কোডের ট্রেলিস রেখাচিত্র দ্বারা সংজ্ঞায়িত করা হয়। যেহেতু শাখা মেট্রিক্স সবসময়ই থাকে, তাই মেট্রিক কাউন্টারগুলিকে অতিরিক্ত প্রবাহ থেকে রক্ষা করার জন্য অবশ্যই একটি অতিরিক্ত সার্কিট (ছবিতে দেখানো হয়নি) থাকতে হবে। একটি বিকল্প পদ্ধতি যা পথ মেট্রিক বৃদ্ধি পর্যবেক্ষণের প্রয়োজনীয়তা দূর করে তা হল পথ মেট্রিকগুলিকে "রোল ওভার" করার অনুমতি দেওয়া; এই পদ্ধতিটি ব্যবহার করার জন্য এটি নিশ্চিত করা প্রয়োজন যে পথ মেট্রিক অ্যাকিউমুলেটরগুলিতে যথেষ্ট বিট রয়েছে যাতে "সেরা" এবং "খারাপ" মানগুলি একে অপরের 2 (এন-1) এর মধ্যে না আসে। তুলনা সার্কিট মূলত অপরিবর্তিত। "সেরা" পথ মেট্রিকের বৃদ্ধির হার পর্যবেক্ষণ করে আগত বিট প্রবাহে শব্দের মাত্রা পর্যবেক্ষণ করা সম্ভব। এটি করার একটি সহজ উপায় হল একটি একক অবস্থান বা "অবস্থা" পর্যবেক্ষণ করা এবং সঞ্চয়ের সীমার মধ্যে চারটি বিচ্ছিন্ন স্তরের মধ্য দিয়ে এটিকে "ঊর্ধ্বমুখী" হতে দেখা। এই প্রতিটি প্রান্তিকের মধ্য দিয়ে উপরের দিকে যাওয়ার সাথে সাথে একটি কাউন্টার বৃদ্ধি করা হয় যা আগত সংকেতে উপস্থিত "শব্দ" প্রতিফলিত করে। ট্রেসব্যাক ইউনিট (টিবিইউ) ব্যাক-ট্রেস ইউনিট পিএমইউ দ্বারা নেওয়া সিদ্ধান্তগুলি থেকে একটি (প্রায়) সর্বাধিক-উপার্জনের পথ পুনরুদ্ধার করে। যেহেতু এটি বিপরীত দিকে কাজ করে, একটি ভিটারবি ডিকোডার একটি সঠিক ক্রম পুনর্গঠনের জন্য একটি এফ. আই. এল. ও (ফার্স্ট-ইন-লাস্ট-আউট) বাফার নিয়ে গঠিত। মনে রাখবেন যে ছবিতে দেখানো বাস্তবায়নের জন্য দ্বিগুণ ফ্রিকোয়েন্সি প্রয়োজন। কিছু কৌশল রয়েছে যা এই প্রয়োজনীয়তা দূর করে। বাস্তবায়নের বিষয়গুলি সফ্ট ডিসিশন ডিকোডিং-এর জন্য কোয়ান্টাইজেশন নরম ডিসিশন ডিকোডিং-এর সুবিধাগুলি সম্পূর্ণরূপে কাজে লাগানোর জন্য, ইনপুট সংকেতকে সঠিকভাবে পরিমাপ করতে হবে। সর্বোত্তম কোয়ান্টাইজেশন জোন প্রস্থ নিম্নলিখিত সূত্র দ্বারা সংজ্ঞায়িত করা হয়ঃ যেখানে একটি শব্দ শক্তি বর্ণালী ঘনত্ব, এবং কে নরম সিদ্ধান্তের জন্য বেশ কয়েকটি বিট। ইউক্লিডীয় মেট্রিক গণনা কোড বর্ণমালায় প্রাপ্ত এবং প্রকৃত প্রতীকগুলির মধ্যে বর্গাকার আদর্শ () দূরত্বকে রৈখিক যোগফল/পার্থক্য আকারে আরও সরলীকৃত করা যেতে পারে, যা এটিকে গণনামূলকভাবে কম নিবিড় করে তোলে। একটি 1/2 কনভোলিউশনাল কোড বিবেচনা করুন, যা প্রতিটি ইনপুট বিটের (1 বা 0) জন্য 2 বিট (00,01,10 বা 11) উৎপন্ন করে। এই রিটার্ন-টু-জিরো সংকেতগুলি পাশে দেখানো অ-রিটার্ন-টু-জিরো আকারে অনুবাদ করা হয়। প্রতিটি প্রাপ্ত প্রতীক ভেক্টর আকারে vr = {r0, r1} হিসাবে প্রতিনিধিত্ব করা যেতে পারে, যেখানে r0 এবং r1 নরম সিদ্ধান্তের মান, যার মাত্রা প্রাপ্ত ভেক্টরের যৌথ নির্ভরযোগ্যতা নির্দেশ করে, vr। একইভাবে, কোড বর্ণমালার প্রতিটি প্রতীক ভেক্টর vi = {±1, ±1} দ্বারা প্রতিনিধিত্ব করা যেতে পারে। ইউক্লিডীয় দূরত্ব মেট্রিকের প্রকৃত গণনাটি হলঃ প্রতিটি বর্গ পদ একটি আদর্শ দূরত্ব, যা প্রতীকটির শক্তিকে চিত্রিত করে। উদাহরণস্বরূপ, চিহ্ন vi = {±1, ±1}-এর শক্তি হিসাবে গণনা করা যেতে পারে সুতরাং, কোড বর্ণমালার সমস্ত চিহ্নের শক্তি পদটি ধ্রুবক ((স্বাভাবিক) মান 2)। অ্যাড-কম্পেয়ার-সিলেক্ট (এসিএস) অপারেশন প্রাপ্ত প্রতীক। |vr।। এবং কোড বর্ণমালার যে কোনও 2 টি প্রতীকের মধ্যে মেট্রিক দূরত্বের তুলনা করে যার পথগুলি সংশ্লিষ্ট ট্রেলিসের একটি নোডে একত্রিত হয়,। |vi (0)।। এবং। |vi (1)।।। কিন্তু, উপর থেকে আমরা জানি যে vi-এর শক্তি ধ্রুবক (2-এর (স্বাভাবিক) মানের সমান), এবং উভয় ক্ষেত্রেই vr-এর শক্তি একই। এটি 2 (মধ্য) বিন্দু গুণফল পদগুলির মধ্যে একটি মিনিমা ফাংশনের তুলনাকে হ্রাস করে, যেহেতু ঋণাত্মক সংখ্যার উপর একটি ক্রিয়াকে ধনাত্মক পরিমাণের সমতুল্য ক্রিয়া হিসাবে ব্যাখ্যা করা যেতে পারে। প্রতিটি ডট প্রোডাক্ট টার্মকে প্রসারিত করা যেতে পারে যেখানে, প্রতিটি শব্দের চিহ্নগুলি প্রতীকের উপর নির্ভর করে, vi (0) এবং vi (1), তুলনা করা হচ্ছে। সুতরাং, শাখা মেট্রিক গণনা করার জন্য বর্গ ইউক্লিডীয় মেট্রিক দূরত্ব গণনা একটি সহজ যোগ/বিয়োগ ক্রিয়াকলাপের মাধ্যমে করা যেতে পারে। ট্রেসব্যাকের সাধারণ পদ্ধতি হল সীমাবদ্ধতার দৈর্ঘ্যের পাঁচগুণ (5 (কে-1)) পর্যন্ত পথের মেট্রিক্স সংগ্রহ করা, সর্বাধিক সঞ্চিত ব্যয় সহ নোডটি খুঁজে বের করা এবং এই নোড থেকে ট্রেসব্যাক শুরু করা। একটি কনভোলিউশনাল কোডের স্মৃতির (সীমাবদ্ধ দৈর্ঘ্য কে-1) পাঁচগুণ গভীরতার একটি ছাঁটাইয়ের থাম্বের সাধারণভাবে ব্যবহৃত নিয়মটি শুধুমাত্র 1/2 হারের কোডের জন্য সঠিক। একটি নির্বিচারে হারের জন্য, থাম্বের একটি সঠিক নিয়ম হল 2.5 (কে-1)/(1-আর) যেখানে আর হল কোড হার। যাইহোক, যে নোডটি সর্বাধিক ব্যয় (বৃহত্তম বা ক্ষুদ্রতম ইন্টিগ্রাল পাথ মেট্রিক) সংগ্রহ করেছে তার গণনায় বেশ কয়েকটি (সাধারণত 2কে-1) সংখ্যার ম্যাক্সিমা বা মিনিমা খুঁজে বের করা জড়িত, যা এমবেডেড হার্ডওয়্যার সিস্টেমে প্রয়োগ করার সময় সময়সাপেক্ষ হতে পারে। বেশিরভাগ যোগাযোগ ব্যবস্থা ভিটারবি ডিকোডিং ব্যবহার করে যার মধ্যে নির্দিষ্ট আকারের ডেটা প্যাকেট থাকে, যার মধ্যে ডেটা প্যাকেটের শুরুতে বা/এবং শেষে একটি নির্দিষ্ট বিট/বাইট প্যাটার্ন থাকে। পরিচিত বিট/বাইট প্যাটার্নকে রেফারেন্স হিসাবে ব্যবহার করে, স্টার্ট নোডকে একটি নির্দিষ্ট মান নির্ধারণ করা যেতে পারে, যার ফলে ট্রেসব্যাকের সময় একটি নিখুঁত সর্বাধিক সম্ভাব্যতা পথ পাওয়া যায়। সীমাবদ্ধতা একটি ভিটারবি ডিকোডারের একটি শারীরিক বাস্তবায়ন ইনপুট সংকেত, শাখা এবং পথ মেট্রিক্স এবং সীমাবদ্ধ ট্রেসব্যাক দৈর্ঘ্যের পরিমাণের কারণে একটি সঠিক সর্বাধিক-জীবিকা প্রবাহ প্রদান করবে না। ব্যবহারিক বাস্তবায়নগুলি আদর্শের 1 ডিবি-র মধ্যে পৌঁছায়। একটি ভিটারবি ডিকোডারের আউটপুট, যখন একটি যোগাত্মক গাউসিয়ান চ্যানেল দ্বারা ক্ষতিগ্রস্ত একটি বার্তা ডিকোড করে, তখন ত্রুটিগুলি ত্রুটি বিস্ফোরণে গোষ্ঠীভুক্ত হয়। একক-ত্রুটি-সংশোধনকারী কোডগুলি একা এই ধরনের বিস্ফোরণগুলি সংশোধন করতে পারে না, তাই কনভোলিউশনাল কোড এবং ভিটারবি ডিকোডারকে অবশ্যই গ্রহণযোগ্য হারে ত্রুটিগুলি হ্রাস করার জন্য যথেষ্ট শক্তিশালী ডিজাইন করতে হবে, অথবা বিস্ফোরণ ত্রুটি-সংশোধনকারী কোডগুলি অবশ্যই ব্যবহার করতে হবে। পাঙ্কচার্ড কোডগুলি সাধারণত পাঙ্কচার্ড কোডগুলির একটি হার্ডওয়্যার ভিটারবি ডিকোডার এমনভাবে প্রয়োগ করা হয়ঃ একটি ডিপাঙ্কচারার, যা ইনপুট স্ট্রিমটিকে প্রবাহে রূপান্তরিত করে যা বিটগুলি মুছে ফেলা হয়েছিল এমন জায়গাগুলিতে ERASE চিহ্ন সহ একটি মূল (অ-পাঙ্কচার্ড) স্ট্রিমের মতো দেখায়। এই ই. আর. এ. এস. ই চিহ্নগুলি বোঝার জন্য একটি মৌলিক ভিটারবি ডিকোডার (অর্থাৎ, শাখা মেট্রিক গণনার জন্য এগুলি ব্যবহার না করা)। সফ্টওয়্যার বাস্তবায়ন সর্বাধিক সময়সাপেক্ষ ক্রিয়াকলাপগুলির মধ্যে একটি হল একটি এসিএস প্রজাপতি, যা সাধারণত ডিকোডিংয়ের সময়কে দ্রুততর করার জন্য একটি সমাবেশ ভাষা এবং উপযুক্ত নির্দেশ সেট এক্সটেনশন (যেমন এস. এস. ই. 2) ব্যবহার করে প্রয়োগ করা হয়। প্রয়োগ ভিটারবি ডিকোডিং অ্যালগরিদম নিম্নলিখিত ক্ষেত্রগুলিতে ব্যাপকভাবে ব্যবহৃত হয়ঃ রেডিও যোগাযোগঃ ডিজিটাল টিভি (এটিএসসি, কিউএএম, ডিভিবি-টি ইত্যাদি)। ), রেডিও রিলে, স্যাটেলাইট কমিউনিকেশন, অপেশাদার রেডিওর জন্য পিএসকে31 ডিজিটাল মোড। ডিকোডিং ট্রেলিস-কোডেড মড্যুলেশন (টিসিএম), 3 কিলোহার্জ-ব্যান্ডউইথ এনালগ টেলিফোন লাইনের মধ্যে উচ্চ বর্ণালী দক্ষতা চেপে ধরার জন্য টেলিফোন-লাইন মডেমে ব্যবহৃত কৌশল। হার্ড ডিস্ক ড্রাইভের মতো কম্পিউটার স্টোরেজ ডিভাইস। স্বয়ংক্রিয় বক্তৃতা স্বীকৃতি রেফারেন্স বাহ্যিক লিঙ্ক ভিটারবি ডিকোডিংয়ের পাশাপাশি একটি গ্রন্থপঞ্জির বিবরণ। হার্ডওয়্যার বাস্তবায়নের সমস্যাগুলির উপর ফোকাস সহ ভিটারবি অ্যালগরিদম ব্যাখ্যা। আর = 1/6 কে = শনিতে ক্যাসিনি মিশনের জন্য 15 কোডিং। অপ্টিমাইজড সফ্টওয়্যারের অনলাইন জেনারেটর ভিটারবি ডিকোডার (জিপিএল)। চারটি স্ট্যান্ডার্ড কোডের জন্য জিপিএল ভিটারবি ডিকোডার সফ্টওয়্যার। একটি কে = 24 ভিটারবি ডিকোডারের বর্ণনা, যা ব্যবহারিক ব্যবহারে সর্বকালের বৃহত্তম বলে মনে করা হয়। জেনেরিক ভিটারবি ডিকোডার হার্ডওয়্যার (জিপিএল)। ডেটা ট্রান্সমিশনে ত্রুটি সনাক্তকরণ এবং সংশোধন উচ্চ-গুরুত্বপূর্ণ নিবন্ধ