تفاوت میان نسخه‌های «کد همینگ»

جز
ویرایش به‌وسیلهٔ ابرابزار:
جز (ویرایش به‌وسیلهٔ ابرابزار:)
{{بهبود منبع}}
در [[مخابرات]]، کد همینگ، کد تصحیح خطای خطی می‌باشد که به افتخار [[ریچارد همینگ]]، مخترع آن گذاشته شده‌است. کدهای همینگ می‌توانند همزمان ۲ بیت خطا را شناسایی کنند و ۱ بیت خطا را تصحیح کنند؛ از طرفی [[:en:Parity_bit|parity code]] به تنهایی نمی‌تواند خطا‌هاخطاها را تصحیح کند و فقط فرد تعداد بیت از خطاها را تشخیص می‌دهد.<ref>{{Cite journal|date=2018-12-09|title=Hamming code|url=https://en.wikipedia.org/w/index.php?title=Hamming_code&oldid=872897501|journal=Wikipedia|language=en}}</ref>ریچارد همینگ، این متد را در سال ۱۹۵۰ ابداع کرد به عنوان روشی که تصحیح خطا را به صورت اتوماتیک انجام می‌داد؛ او در مقالهٔ اصلی خود، [[:en:Hamming(7,4)|کدهای همینگ(۷٬۴)]] را مورد بررسی قرار می‌دهد که سه بیت توازن(parity) به دادهٔ چهار بیتی اضافه می‌کند.<ref>{{Cite journal|date=2018-12-09|title=Hamming code|url=https://en.wikipedia.org/w/index.php?title=Hamming_code&oldid=872897501|journal=Wikipedia|language=en}}</ref>
 
از لحاظ ریاضی، کد‌هایکدهای همینگ کلاسی از کدهای خطی باینری هستند.
<ref>{{Cite journal|date=2018-12-09|title=Hamming code|url=https://en.wikipedia.org/w/index.php?title=Hamming_code&oldid=872897501|journal=Wikipedia|language=en}}</ref>ریچارد همینگ، این متد را در سال ۱۹۵۰ ابداع کرد به عنوان روشی که تصحیح خطا را به صورت اتوماتیک انجام می‌داد؛ او در مقاله‌ی اصلی خود، [[:en:Hamming(7,4)|کد‌های همینگ(۷،۴)]] را مورد بررسی قرار می‌دهد که‌ سه بیت توازن(‌parity) به داده‌ی چهار بیتی اضافه می‌کند.<ref>{{Cite journal|date=2018-12-09|title=Hamming code|url=https://en.wikipedia.org/w/index.php?title=Hamming_code&oldid=872897501|journal=Wikipedia|language=en}}</ref>
 
برای هر عدد صحیح ''r'' ≥ 2۲ وجود دارد کدی[[:en:Block_code#The_block_length_n|(Block length)]] با طول ''n'' = 2<sup>''r''</sup> − 1۱ پیامی [[:en:Block_code#The_message_length_k|(Message length)]] به طول ''k'' = 2<sup>''r''</sup> − ''r'' − 1۱. از این رو برآورد ما از متد همینگ اینگونه به دست می‌آید:( ''R'' = ''k'' / ''n'' = 1۱ − ''r'' / (2<sup>''r''</sup> − 1۱ یعنی بیشترین احتمال برای کدهاییست که در کمترین فاصله از سه هستند. (کمترین تعداد بیت هاییبیت‌هایی که باید تغییر کنند تا از کدی، کد معتبر دیگری تولید کنیم، سه بیت است.)
از لحاظ ریاضی، کد‌های همینگ کلاسی از کدهای خطی باینری هستند.
 
ماتریس سنجش توازن[[:en:Parity-check_matrix|(parity-check matrix)]]<nowiki/>برای کد‌هایکدهای همینگ از تمام ستون‌های به طول ''r'' ناصفر ساخته می‌شود؛ ستون هایستون‌های این ماتریس دوبه دو مستقل خطی هستند.
برای هر عدد صحیح ''r'' ≥ 2 وجود دارد کدی[[:en:Block_code#The_block_length_n|(Block length)]] با طول ''n'' = 2<sup>''r''</sup> − 1 پیامی [[:en:Block_code#The_message_length_k|(Message length)]] به طول ''k'' = 2<sup>''r''</sup> − ''r'' − 1. از این رو برآورد ما از متد همینگ اینگونه به دست می‌آید:( ''R'' = ''k'' / ''n'' = 1 − ''r'' / (2<sup>''r''</sup> − 1 یعنی بیشترین احتمال برای کدهاییست که در کمترین فاصله از سه هستند.(کمترین تعداد بیت هایی که باید تغییر کنند تا از کدی، کد معتبر دیگری تولید کنیم، سه بیت است.)
 
در این روش بیت هایبیت‌های کمی به دیتاها اضافه می‌شود؛ که این یعنی همینگ کد به شرط کم بودن خطا در داده‌ها، می‌تواند خطا‌هاخطاها را تشخیص داده و تصحیح کند. از کاربردهای این روش می‌توان به حافظه‌یحافظهٔ کامپیوتر [[حافظه ئی‌سی‌سی|ECC memory]] اشاره کرد؛ وقتی که بیت‌خطا‌هابیت‌خطاها بسیار کم باشند، کدهای همینگ آن را مدیریت می‌کنند.
ماتریس سنجش توازن[[:en:Parity-check_matrix|(parity-check matrix)]]<nowiki/>برای کد‌های همینگ از تمام ستون‌های به طول ''r'' ناصفر ساخته می‌شود؛ ستون های این ماتریس دوبه دو مستقل خطی هستند.
 
در این روش بیت های کمی به دیتاها اضافه می‌شود؛ که این یعنی همینگ کد به شرط کم بودن خطا در داده‌ها، می‌تواند خطا‌ها را تشخیص داده و تصحیح کند. از کاربردهای این روش می‌توان به حافظه‌ی کامپیوتر [[حافظه ئی‌سی‌سی|ECC memory]] اشاره کرد؛ وقتی که بیت‌خطا‌ها بسیار کم باشند، کدهای همینگ آن را مدیریت می‌کنند.
 
در نتیجه مخابره قابل اطمینان در صورتی که فاصله همینگ بین رشته بیت فرستنده و گیرنده یک یا کمتر از یک باشد، ممکن می‌شود.
 
== کد بدون وزن همینگ ==
دسته‌ای از کدها برای تشخیص و تصحیح خطا در ارسال اطلاعات استفاده می‌شوند.می‌شوند؛ که به آنها کد همینگ می‌گویند. در این کدها حداقل اختلافی که بین دوکد نمایشی وجودداردفاصله همینگ نامند.
 
ما در اینجا کد همینگ با حداقل فاصله 3۳ را توضیح می‌دهیم. یعنی بیتهایی را که به آنها اضافه می‌کنیم 3۳ بیت می‌باشد. چون در کد همینگ به منظور تشخیص و تصحیح خطا باید بیتهایی را به کدمان اضافه کنیم.
 
اگر بخواهیم کد NBCD را با حداقل فاصله 3۳ ارسال کنیم. باید به کد NBCD ،NBCD، سه بیت اضافه کنیم.کنیم؛ که اطلاعات ارسالی به صورت زیر می‌شود.
C1 c2 b3 c4 b5 b6 b7
که در اینجا بیت c1 و c2 و c4 سه بیتی هستند که به کدمان اضافه می‌شوند و به آنها بیتهای الحاقی می‌گویند و به بیتهای b3 و b5 و b6 و b7 بیتهای اطلاعاتی می‌گویند.
{C1={ b3, b5 , b7} c2={ b3 , b6 , b7 } c4={ b5 , b6 , b7 }
 
که در آنها اگر تعداد یک‌ها زوج بود حاصل c برابر صفر و اگر فرد بود برابر یک می‌شو. د.
 
به عنوان مثال رقم 5۵ در کد NBCD را به روش زیر ارسال می‌کنیم.
 
c1=? c2=? b3=0 c4=? b5=1 b6=0 b7=1۱
 
c1={ b3 , b5 , b7 }= { 0,1،1۰٬۱٬۱} == ==> c1=0۰
 
1۱= c2={ b3 , b6 , b7 }= { 0,0،1۰٬۰٬۱ }== ==> c2
 
0۰= c4={ b5 , b6 , b7 }= { 1,0،1۱٬۰٬۱ }== ==> c4
 
پس بر اساس اعداد به دست آمده عدد 5۵ هنگام ارسال به صورت 0100101۰۱۰۰۱۰۱ ارسال می‌شود.
 
== جستارهای وابسته ==
۱

ویرایش