کد همینگ
From Wikipedia, the free encyclopedia
در مخابرات، کد همینگ، کد تصحیح خطای خطی میباشد که به افتخار ریچارد همینگ، مخترع آن گذاشته شدهاست. کدهای همینگ میتوانند همزمان ۲ بیت خطا را شناسایی کنند و ۱ بیت خطا را تصحیح کنند؛ از طرفی parity code به تنهایی نمیتواند خطاها را تصحیح کند و فقط فرد تعداد بیت از خطاها را تشخیص میدهد.[1] ریچارد همینگ، این متد را در سال ۱۹۵۰ ابداع کرد به عنوان روشی که تصحیح خطا را به صورت اتوماتیک انجام میداد؛ او در مقالهٔ اصلی خود، کدهای همینگ(۷٬۴) را مورد بررسی قرار میدهد که سه بیت توازن(parity) به دادهٔ چهار بیتی اضافه میکند.[1]
از لحاظ ریاضی، کدهای همینگ کلاسی از کدهای خطی باینری هستند.
برای هر عدد صحیح r ≥ ۲ وجود دارد کدی(Block length) با طول n = 2r − ۱ پیامی (Message length) به طول k = 2r − r − ۱. از این رو برآورد ما از متد همینگ اینگونه به دست میآید:(R = k / n = ۱ − r / (2r − ۱ یعنی بیشترین احتمال برای کدهایی است که در کمترین فاصله از سه هستند. (کمترین تعداد بیتهایی که باید تغییر کنند تا از کدی، کد معتبر دیگری تولید کنیم، سه بیت است)
ماتریس سنجش توازن(parity-check matrix)برای کدهای همینگ از تمام ستونهای به طول r ناصفر ساخته میشود؛ ستونهای این ماتریس دوبه دو مستقل خطی هستند.
در این روش بیتهای کمی به دیتاها اضافه میشود؛ که این یعنی همینگ کد به شرط کم بودن خطا در دادهها، میتواند خطاها را تشخیص داده و تصحیح کند. از کاربردهای این روش میتوان به حافظهٔ کامپیوتر ECC memory اشاره کرد؛ وقتی که بیتخطاها بسیار کم باشند، کدهای همینگ آن را مدیریت میکنند.
در نتیجه مخابره قابل اطمینان در صورتی که فاصله همینگ بین رشته بیت فرستنده و گیرنده یک یا کمتر از یک باشد، ممکن میشود.