Guruswami–Sudan list decoding algorithm
কোডিং তত্ত্বে, তালিকা ডিকোডিং অনেক ত্রুটির উপস্থিতিতে ত্রুটি-সংশোধন কোডগুলির অনন্য ডিকোডিংয়ের একটি বিকল্প। যদি কোনও কোডের আপেক্ষিক দূরত্ব থাকে, তবে নীতিগতভাবে একটি এনকোডেড বার্তা পুনরুদ্ধার করা সম্ভব যখন কোডওয়ার্ড প্রতীকগুলির ভগ্নাংশ পর্যন্ত দূষিত হয়। কিন্তু যখন ত্রুটির হার এর চেয়ে বেশি হবে, তখন এটি সাধারণভাবে সম্ভব হবে না। তালিকা ডিকোডিং ডিকোডারকে এনকোড করা হতে পারে এমন বার্তাগুলির একটি সংক্ষিপ্ত তালিকা আউটপুট করার অনুমতি দিয়ে সেই সমস্যাটি অতিক্রম করে। তালিকা ডিকোডিং ত্রুটির ভগ্নাংশের চেয়ে বেশি সংশোধন করতে পারে। তালিকা ডিকোডিংয়ের জন্য অনেক পলিনোমিয়াল-টাইম অ্যালগরিদম রয়েছে। এই নিবন্ধে, আমরা প্রথমে রিড-সলোমন (আরএস) কোডগুলির জন্য একটি অ্যালগরিদম উপস্থাপন করি যা ত্রুটিগুলি সংশোধন করে এবং মধু সুদানের কারণে হয়। পরবর্তীকালে, আমরা উন্নত গুরুস্বামী-সুদান তালিকা ডিকোডিং অ্যালগরিদম বর্ণনা করি, যা ত্রুটিগুলি সংশোধন করতে পারে। এখানে বিভিন্ন অ্যালগরিদমের জন্য হার আর এবং দূরত্বের একটি প্লট রয়েছে। https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/81/Graph.jpg অ্যালগরিদম 1 (সুদানের তালিকা ডিকোডিং অ্যালগরিদম) সমস্যা বিবৃতি ইনপুটঃ একটি ক্ষেত্র; এন স্বতন্ত্র জোড়া উপাদান; এবং পূর্ণসংখ্যা এবং। আউটপুটঃ সন্তোষজনক সমস্ত ফাংশনের একটি তালিকা সর্বাধিক মাত্রায় একটি বহুপদী সুদানের অ্যালগরিদমকে আরও ভালভাবে বোঝার জন্য, কেউ প্রথমে অন্য একটি অ্যালগরিদম জানতে চাইতে পারে যা পূর্ববর্তী সংস্করণ বা তালিকা ডিকোডিং আরএস কোডের জন্য অ্যালগরিদমের মৌলিক সংস্করণ হিসাবে বিবেচিত হতে পারে-বার্লেক্যাম্প-ওয়েলচ অ্যালগরিদম। ওয়েলচ এবং বার্লেক্যাম্প প্রাথমিকভাবে একটি অ্যালগরিদম নিয়ে এসেছিলেন যা বহুপদী সময়ে সমস্যার সমাধান করতে পারে। সুদানের অ্যালগরিদমের প্রক্রিয়াটি বার্লেক্যাম্প-ওয়েলচ অ্যালগরিদমের অ্যালগরিদমের প্রায় একই রকম, প্রথম ধাপটি ছাড়া, কেউ সীমাবদ্ধ ডিগ্রির একটি দ্বি-বৈকল্পিক বহুপদী গণনা করতে চায়। রিড-সলোমন কোডের জন্য সুদানের তালিকা ডিকোডিং অ্যালগরিদম যা বার্লেক্যাম্প এবং ওয়েলচ অ্যালগরিদমের একটি উন্নতি, এর মাধ্যমে সমস্যার সমাধান করতে পারে। এই বাউন্ড অনন্য ডিকোডিং বাউন্ডের চেয়ে ভাল। অ্যালগরিদম সংজ্ঞা 1 (ওজনযুক্ত ডিগ্রি) ওজনের জন্য, মনোমিয়ালের-ওজনযুক্ত ডিগ্রি হল। একটি বহুপদীর-ওজনযুক্ত ডিগ্রি হল সর্বাধিক, অ-শূন্য সহগ সহ মনোমিয়ালগুলির উপর, মনোমিয়ালের-ওজনযুক্ত ডিগ্রি। উদাহরণস্বরূপ,-ডিগ্রি 7 অ্যালগরিদম রয়েছেঃ ইনপুটঃ; {}/* প্যারামিটার l, m পরে সেট করা হবে। */ধাপ 1: একটি অ-শূন্য দ্বি-বৈকল্পিক বহুপদী সন্ধান করুন যা সর্বাধিক-ওজনযুক্ত ডিগ্রি অর্জন করে। অপরিবর্তনীয় ফ্যাক্টরের মধ্যে ফ্যাক্টর Q। ধাপ 3। সমস্ত পলিনোমিয়ালগুলি এমনভাবে আউটপুট করুন যা Q-এর একটি ফ্যাক্টর এবং বিশ্লেষণের কমপক্ষে t মানগুলির জন্য একজনকে প্রমাণ করতে হবে যে উপরের অ্যালগরিদমটি পলিনোমিয়াল সময়ে চলে এবং সঠিক ফলাফল দেয়। নিম্নলিখিত দাবির সেট প্রমাণ করে এটি করা যেতে পারে। দাবি 1: যদি একটি সন্তোষজনক ফাংশন (2) বিদ্যমান থাকে, তবে কেউ এটি বহুপদী সময়ে খুঁজে পেতে পারে। প্রমাণঃ লক্ষ্য করুন যে-ওয়েটেড ডিগ্রির একটি দ্বি-বৈকল্পিক বহুপদকে অনন্যভাবে এভাবে লেখা যেতে পারে। তারপর প্রত্যেকের জন্য সীমাবদ্ধতাগুলি সন্তুষ্টকারী সহগগুলি খুঁজে বের করতে হবে। এটি অজানা {} সমীকরণের একটি রৈখিক সেট। পলিনোমিয়াল সময়ে গাউসিয়ান এলিমিনেশন ব্যবহার করে একটি সমাধান খুঁজে পাওয়া যায়। দাবি 2: যদি সন্তোষজনক কোনও ফাংশন থাকে (2) প্রমাণঃ একটি অ-শূন্য সমাধানের অস্তিত্ব নিশ্চিত করার জন্য, সহগের সংখ্যা সীমাবদ্ধতার সংখ্যার চেয়ে বেশি হওয়া উচিত। ধরে নিন যে ইন-এর সর্বোচ্চ ডিগ্রি হল m এবং ইন-এর সর্বোচ্চ ডিগ্রি হল। তারপর এর মাত্রা সর্বাধিক হবে। একজনকে দেখতে হবে যে রৈখিক ব্যবস্থাটি সমজাতীয়। সেটিংটি সমস্ত রৈখিক সীমাবদ্ধতাকে সন্তুষ্ট করে। তবে এটি (2) কে সন্তুষ্ট করে না, কারণ সমাধানটি অভিন্নভাবে শূন্য হতে পারে। একটি অ-শূন্য সমাধানের অস্তিত্ব নিশ্চিত করার জন্য, একজনকে নিশ্চিত করতে হবে যে রৈখিক ব্যবস্থায় অজানা সংখ্যা কত হবে, যাতে একজন অ-শূন্য পেতে পারে। যেহেতু এই মানটি n এর চেয়ে বড়, তাই সীমাবদ্ধতার চেয়ে বেশি চলক রয়েছে এবং তাই একটি অ-শূন্য সমাধান বিদ্যমান। দাবি 3: যদি একটি ফাংশন সন্তোষজনক হয় (2) এবং ফাংশন সন্তোষজনক হয় (1) এবং তারপর প্রমাণকে ভাগ করেঃ একটি ফাংশন বিবেচনা করুন। এটি একটি বহুপদী, এবং যুক্তি দেয় যে এটির সর্বাধিক ডিগ্রি রয়েছে। এর যে কোনও একক সংখ্যা বিবেচনা করুন। যেহেতু সর্বাধিক-ওজনযুক্ত ডিগ্রি রয়েছে, তাই এটি বলা যেতে পারে। সুতরাং শব্দটি সর্বাধিক মাত্রায় একটি বহুপদী। সুতরাং সর্বাধিক ডিগ্রি রয়েছে পরবর্তী যুক্তি যা অভিন্নভাবে শূন্য। যেহেতু শূন্য যখনই হয়, কেউ বলতে পারে যে কঠোরভাবে পয়েন্টের চেয়ে বড়ের জন্য এটি শূন্য। সুতরাং এর ডিগ্রির চেয়ে বেশি শূন্য রয়েছে এবং তাই অভিন্নভাবে শূন্য, যা এবং-এর জন্য সর্বোত্তম মান খুঁজে বের করার ইঙ্গিত দেয়। লক্ষ্য করুন যে এবং একটি প্রদত্ত মানের জন্য, কেউ সবচেয়ে ছোটটি গণনা করতে পারে যার জন্য দ্বিতীয় শর্তটি ধারণ করে দ্বিতীয় শর্তটি বিনিময় করে একজন সর্বাধিক এই মানটিকে প্রথম শর্তে প্রতিস্থাপন করতে পারে অন্তত একজন হতে পারে পরবর্তী অজানা প্যারামিটারের উপরের সমীকরণটি হ্রাস করুন। সমীকরণের ব্যুৎপত্তি গ্রহণ করে এবং সেটিকে শূন্যের সমতুল্য করে এটি করা যেতে পারে। এটি করার মাধ্যমে যে কেউ মানটি ফিরে পাবে এবং যে কেউ অ্যালগরিদম 2 পাবে (গুরুস্বামী-সুদান তালিকা ডিকোডিং অ্যালগরিদম) সংজ্ঞা মূল্যায়ন সেট এবং একটি ধনাত্মক পূর্ণসংখ্যা সহ সীমাবদ্ধ ক্ষেত্রের উপর একটি রিড-সলোমন কোড বিবেচনা করুন, গুরুস্বামী-সুদান তালিকা ডিকোডার একটি ভেক্টরকে ইনপুট হিসাবে গ্রহণ করে এবং ডিগ্রির বহুপদীগুলির একটি তালিকা আউটপুট করে যা কোডওয়ার্ডের সাথে 1 থেকে 1 মিল রয়েছে। ধারণাটি হল দ্বি-বৈকল্পিক বহুপদের উপর আরও বিধিনিষেধ যুক্ত করা যার ফলে শিকড়ের সংখ্যা সহ সীমাবদ্ধতা বৃদ্ধি পায়। গুণিতক একটি দ্বি-বৈকল্পিক বহুপদের গুণিতক শূন্য থাকে যার কোনও ডিগ্রি নেই, যেখানে x-ডিগ্রি যে কোনও x পদের সর্বাধিক ডিগ্রি হিসাবে সংজ্ঞায়িত করা হয়। https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig1.jpg অতএব, (0,0)-এ 1-এর গুণিতক শূন্য। যাক। https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig2.jpg অতএব, (0,0)-এ 1-এর গুণিতক শূন্য। ধরা যাক https://wiki.cse.buffalo.edu/cse545/sites/wiki.cse.buffalo.edu.cse545/files/76/Fig3.jpg সুতরাং, (0,0)-এ 2-এর গুণফল শূন্য। একইভাবে, যদি তারপর হয়, তার গুণফল 2 এ শূন্য থাকে। গুণের সাধারণ সংজ্ঞার মূল রয়েছে যদি কখন গুণের শূন্য থাকে। অ্যালগরিদম প্রেরিত কোডওয়ার্ডটি প্রেরিত কোডওয়ার্ডের সাপোর্ট সেট এবং প্রাপ্ত শব্দটি গ্রহণযোগ্য শব্দ হতে দিন অ্যালগরিদমটি নিম্নরূপঃ একটি প্রাপ্ত ভেক্টরের জন্য, সর্বাধিক ওজনযুক্ত ডিগ্রি সহ একটি অ-শূন্য দ্বি-বৈকল্পিক বহুপদ তৈরি করুন যার প্রতিটি পয়েন্টে বহুগুণের শূন্য থাকে যেখানে ফ্যাক্টরাইজেশন পদক্ষেপ ফর্মের সমস্ত ফ্যাক্টর এবং কমপক্ষে ডিগ্রির একটি বহুপদ কোথায় এবং তার মানগুলির জন্য সন্ধান করুন মনে রাখবেন যে ডিগ্রির বহুপদগুলি কোডওয়ার্ডের সাথে 1 থেকে 1 মিল রয়েছে। অতএব, এই ধাপটি কোডওয়ার্ডের তালিকা প্রকাশ করে। বিশ্লেষণ ইন্টারপোলেশন ধাপ লেমাঃ ইন্টারপোলেশন ধাপ বোঝায় কোথায় এবং তারপর, (সমীকরণ 1)-এর সহগগুলির উপর সীমাবদ্ধতা যেখানে সমীকরণ 1-এর প্রমাণঃ দ্বিপদী সম্প্রসারণ ব্যবহার করে লেমার প্রমাণঃ বহুপদের গুণিতক শূন্য থাকে যদি এমন হয় যা মান গ্রহণ করতে পারে। সুতরাং, সীমাবদ্ধতার মোট সংখ্যা হল এই যে, নির্বাচনের সংখ্যা ফ্যাক্টরাইজেশন ধাপ প্রস্তাবের সহগগুলির উপর সীমাবদ্ধতাগুলি বোঝায়ঃ যদি এটি প্রমাণের একটি ফ্যাক্টর হয়ঃ যেহেতু, একটি ফ্যাক্টর, যেখানে, অবশিষ্টাংশ দ্বারা ভাগ করলে প্রাপ্ত ভাগফলটি কোথায় তা হিসাবে উপস্থাপন করা যেতে পারে। উপরে যেমন প্রমাণিত হয়েছে, যেখানে এল. এইচ. এস হল সহগের সংখ্যার উপরের সীমা এবং আর. এইচ. এস হল পূর্বে প্রমাণিত লেমা। অতএব, গুরুস্বামী-সুদান তালিকা ডিকোডিং অ্যালগরিদম ত্রুটি পর্যন্ত ডিকোড রিড-সলোমন কোড তালিকাভুক্ত করতে পারে। তথ্যসূত্র https://web.archive.org/web/20100702120650/http:// সি. এস. ই. বুফালো. এডু/~ অত্রি/কোর্স/কোডিং-তত্ত্ব/https://www.cs.cmu.edu ~ ভেনকাটগ/পাবস/পেপারস/লিস্টকোডিং-NOW.pdf http://www.mendeley.com/research/algebraic-softdecision-decoding-reedsolomon-codes আর. জে. ম্যাকএলিস। রিড-সলোমন কোডের জন্য গুরুস্বামী-সুদান ডিকোডিং অ্যালগরিদম। এম সুদান। ত্রুটি-সংশোধন সীমার বাইরে রিড সলোমন কোডগুলির ডিকোডিং। কোডিং তত্ত্ব