H Простая программа на PYTHON для граматического анализа слов и фрагментов текста в черновиках Recovery Mode

Зачем это нужно

Код программы

# -*- coding: utf-8 -*-
import enchant
from enchant.checker import SpellChecker
from enchant.tokenize import EmailFilter, URLFilter

def get(event):
        t=str(l.get(event.widget.curselection()))
        w['key']=0
        w['key']=t
        lab = tk.Label(root, text="", font="Arial 12")
        lab.grid_remove()
        lab = tk.Label(root, text= "Выбран язык -%s--Ввод: поля 1-текст, 2-слово. Вывод поле 3-результат"%t, font="Arial 12")
        lab.grid(row=0, column=0) 

def pravopus():
        t=w['key']
        d = enchant.Dict(t)   
        tex=txt_0.get(1.0, END).strip()
        if len(tex)!=0:
                m=d.check(tex)
                if m:
                        txt.insert(END, "Слово-%s-написано правильно\n"%tex)
                else:
                        txt.insert(END, "Слово--%s- написано не правильно, нужно так-%s- \n"%(tex,str(d.suggest(tex))))
        elif len(tex)==0:
                txt.insert(END, "Введите слово!!!\n")
 

def tokenise():
        try:
                t=w['key']
                txt. delete(1.0, END)
                p= enchant.Dict(t)
                d=  SpellChecker(t,filters=[EmailFilter,URLFilter])
                tex=txt_1.get(1.0, END).strip()
                d.set_text(tex)
                k=0
                for err in d:
                        k=k+1
                        txt.insert(END, "ERROR:",err.word, p.suggest(err.word))
                        txt.insert(END, "\n")
                if k==0:
                        txt.insert(END, 'Предложение написано правильно\n')
        except:
                txt.insert(END, "Ошибка ввода!!!\n")
                pass
 

def clearn():
        txt_0.delete(1.0, END)
        txt_1.delete(1.0, END)
        txt.delete(1.0, END)
import tkinter as tk    
from tkinter import *
root = tk.Tk()       
main_menu = Menu(root)
root.config(menu=main_menu)
file_menu = Menu(main_menu)
main_menu.add_cascade(label="Орфография", menu=file_menu)
file_menu.add_command(label="Проверка блока текста", command=tokenise)
file_menu.  add_command(label="Очистка всех полей", command=clearn)
file_menu.add_command(label="Выход", command=root.destroy)
lab = tk.Label(root, text="Выбирите язык", font="Arial 12")
l = tk.Listbox(root,takefocus=True, width=6,height=5,font="Arial 12")
txt = tk.Text(root, width=64,height=5,font="Arial 12",wrap=WORD)
txt_0 = tk.Text(root, width=64,height=1,font="Arial 12",wrap=WORD)
txt_1 = tk.Text(root, width=64,height=5,font="Arial 12",wrap=WORD)
but = tk.Button(root,text="Проверить слово",command=pravopus)
lab.grid(row=0, column=0)
txt_1.grid(row=1, column=0)
txt_0.grid(row=2, column=0)
txt.grid(row=3, column=0)
l.grid(row=3, column=1)
but.grid(row=4, column=0)
l.insert(END,'en_AU', 'en_GB', 'en_US', 'de_DE', 'fr_FR', 'ru_RU', 'uk_UA')    
l.bind("<<ListboxSelect>>", get)
root.tk.mainloop()
 

Работа программы

Пример работы с английским предложением.

Пример работы с немецким предложением.

1. Python проверка орфографии (windows, linux) — PyEnchant

Как включить подсказки слов и исправление ошибок в Windows 10 при вводе с клавиатуры

06.02.2020&nbsp windows | для начинающих

Функции предикативного ввода текста, когда вам подсказывают набираемое слово и, для некоторых фраз — следующие слова, большинству хорошо знакомы по мобильным устройствам. Однако, такая функция есть и в Windows 10, правда по умолчанию она включена лишь для сенсорной экранной клавиатуры.

В этой инструкции о том, как включить подсказки слов и исправление автоматическое исправление ошибок при вводе текста с аппаратной клавиатуры в Windows 10, русский язык, с некоторыми оговорками, поддерживается.

Включение текстовых предложений при вводе с аппаратной клавиатуры

Для того, чтобы включить функции предикативного ввода при использовании аппаратной клавиатуры Windows 10, выполните следующие шаги:

1. Зайдите в Пуск — Параметры (значок «Шестеренка») или нажмите клавиши Win+I.
2. Перейдите в раздел «Устройства» — «Ввод».
3. Пролистайте до раздела «Аппаратная клавиатура» и включите параметр «Показывать текстовые предложения по мере ввода», «Автоматически исправлять слова при вводе».
4. Также можно включить «Многоязычные текстовые предложения», однако я не вполне разобрался, как именно этот параметр работает, хотя и пробовал вводить предложения, состоящие из слов сразу на нескольких языках.

Готово. Теперь предложение слов будет работать в различных программах, где возможен ввод текста и на сайтах в браузере (но не везде: например, в адресной строке браузера работать не будет).

При начале ввода каких-либо слов вы будете получать предложения как по текущему вводимому слову, так, в некоторых случаях и по следующим словам. При этом для выбора нужного слова не обязательно тянуться за мышкой — достаточно использовать клавиши стрелок (вверх и вправо) и Enter на клавиатуре.

Если кому-то это окажется полезным, то включение и отключение предложений слов при вводе с обычной клавиатуры контролируется в параметром DWORD с именем EnableHwkbPrediction в разделе реестра HKEY_CURRENT_USER\Software\Microsoft\Input\Settings

И об оговорках: опция «Автоматически исправлять слова при вводе», похоже ни на что не влияет, причем я ее проверял и на русском и на английском языке: в обоих случаях, оставалось слово с ошибкой. А при использовании сенсорной клавиатуры Windows 10 исправление исправно работает.

А вдруг и это будет интересно:

Быстро исправить ошибки в тексте (предложениях)

Сегодня почти у каждого студента, а уже и школьника есть компьютер. Он помогает решить много задач, в частности переводить и писать сочинения.

Большинство при этом допускает в тексте (предложениях) ошибки. Их можно исправить автоматически, точнее полуавтоматически.

Чтобы исправить ошибки в тексте (предложениях), можно воспользоваться онлайн сервисами или программами, только первые абсолютно не обращают внимание на пунктуацию.

Программы в этом отношении в частности ВОРД их превосходят. Если вы попали в их число, то установите ворд от Майкрософт офис и быстро исправьте ошибки в предложениях.

Если будут грамматические, программа выделит их красной волнообразной линией (снизу), если пунктуационные (зеленой или синей – зависит от версии).

Также она может исправить ошибки в английском тексте (предложениях), только смените в ней язык проверки правописания. На 100% конечно не получиться – ей не известны новые слова (они появляться постоянно), а где должна стоять запятая, часто решает лишь человек.

Если приходиться писать в интернете, то исправление ошибок не обязательно нужно выполнять дополнительными программами. Установите последние версии браузеров Mozilla Firefox или Internet Explorer и прямо о время написания устраняйте недостатки (подчеркнуты красным).

Для русского языка, самая продвинутая программа исправляющая ошибки в тексте «ОРФО». Она интегрирована в ворд и выполняет свою задачу достаточно хорошо, а вот самостоятельно работает намного хуже.

Единственный недостаток таких проверок (вордом) – она платная. Есть конечно бесплатные аналоги, но они ей уступают. Подробнее обо все этом можно узнать перейдя по ссылкам в тексте выше.

В заключение остановлюсь над английским. Если вам нужно перевести страницу из книги, газеты или журнала, то сделайте скан, а потом вытащите из него текс при помощи «ABBYYFineReader11» или соответствующего онлайн сервиса.

После этого можно воспользоваться онлайн переводчиком. Лучше всего от Google, а после этого можно проверить на ошибки, как я писал выше, лучше сего подойдет ВОРД. К стати сегодня есть приложения работающие и со звуковым сопровождением.

Сообщение без ошибок в WhatsApp: набираем с нормальной клавиатуры

С ультрамегатехнологичных, но очень тесных клавиатурок на экранах смартфонов практически невозможно напечатать сообщение без ошибок и без опечаток, даже если очень нужно.

А если надо сваять текст быстро и грамотно (или хотя бы с минимальным количеством ошибок), то для этого по-прежнему нет ничего лучше, чем полноразмерная клавиатура с настоящими, т. е. физическими, кнопками.

Однако, как написать и отправить такой текст на мобильный? Сначала набирать на компе, потом копировать и пересылать на смартфон или планшет?

Можно, конечно и так. А можно сразу воспользоваться возможностями онлайн-приложения WhatsApp.

Точнее, онлайн-версией WhatsApp, в которой вы просто набираете текст без ошибок (ну, или пытаетесь) с нормальной клавиатуры любого компа и сразу же отправляете его на мобильный адресату. И не важно, у него iPhone или Android.

• #1 — открываем WhatsApp Web своем Windows-ПК или Mac-е

Открываем в любом доступном браузере. Линк вот (к слову, запоминается URL тоже легко — web.whatsapp.com). Лучше сразу сохранить в закладках, если этой версией мессенджера вы планируете пользоваться регулярно.

Первой открывается страница с QR-кодом. Оставляем ее открытой, берем смартфон (или планшет) и затем…

• #2 — синхронизируем WhatsApp Web с обычным мобильным WhatsApp

В мобильном устройстве открываем приложение WhatsApp, заходим в «

После завершения процедуры сканирования онлайн и мобильный WhatsApp-ы синхронизируются автоматически и далее все свои контакты и чаты вы видите уже на компьютере. И переписываться можете уже с большой физической клавиатуры.

Отметим также, что в WhatsApp Web используется система временного входа, поэтому в следующий раз вам тоже надо будет логиниться через QR-код. Не очень удобно, но зато в свой WhatsApp вы можете свободно заходить с разных компьютеров, в том числе и машин «общественного пользования» (в школе, в библиотеке и т.

Обработка ошибок с помощью Python—Справка

Ошибки случаются. Написание скриптов, которое предполагает наличие и обработку ошибок, сохраняет массу времени и ваших сил. Когда инструмент выводит сообщение об ошибке, ArcPy генерирует системную ошибку или исключение. В Python вы можете обеспечить различные структуры и методы для обработки исключений. Конечно, скрипт может не выполниться по причинам, не связанным с инструментом геообработки. Их также следует обнаружить и решить. В следующих разделах предлагаются несколько методов, которые знакомят вас с основами обработки исключений в Python.

Когда инструмент записывает сообщение об ошибке, ArcPy создает исключение arcpy.ExecuteError. Python позволяет написать модуль, который будет запускаться автоматически при возникновении системной ошибки. С помощью этого модуля для обработки ошибок вы сможете получать сообщения об ошибках от ArcPy и реагировать на них. Если скрипт не имеет модуля для обработки ошибок, он завершает выполнение немедленно, что уменьшает его надежность. Модуль обработки ошибок можно использовать для управления ошибками и повышения надежности скриптов.

Выражение try-except

Выражение try-except может быть использовано для разделения программы на шаги, чтобы контролировать выполнение каждого из них и определять места возникновения ошибок. Если ошибка случается внутри выражения try, вызывается исключение и выполняется код в выражении except. Использование выражения except является наиболее простой формой обработки ошибок.

В следующем коде Буфер прекращает работу из-за того, что не был указан обязательный параметр buffer_distance_or_field. Вместо завершения без объяснения причин, выражение except используется для поиска ошибки, ее перехвата и вывода сообщения об ошибке, созданной инструментом Буфер. Обратите внимание, что блок except выполняется только в случае, если в инструменте Буфер происходит ошибка.

import arcpy
import sys
try:
    # Execute the Buffer tool
    #
    arcpy.Buffer_analysis("c:/transport/roads. shp", "c:/transport/roads_buffer.shp")
except Exception:
    e = sys.exc_info()[1]
    print(e.args[0])
    
    # If using this code within a script tool, AddError can be used to return messages 
    #   back to a script tool.  If not, AddError will have no effect.
    arcpy.AddError(e.args[0])

Выражение try имеет опциональный оператор finally, использующийся для задач, которые должны выполняться в любом случае, вне зависимости от появления исключения. В следующем примере дополнительный модуль ArcGIS 3D Analyst включается в оператор finally, что обеспечивает постоянное включение расширения.

class LicenseError(Exception):
    pass
import arcpy
try:
    if arcpy.CheckExtension("3D") == "Available":
        arcpy.CheckOutExtension("3D")
    else:
        # Raise a custom exception
        #
        raise LicenseError
    
    arcpy.env.workspace = "D:/GrosMorne"
    arcpy.HillShade_3d("WesternBrook", "westbrook_hill", 300)
    arcpy.Aspect_3d("WesternBrook", "westbrook_aspect")
except LicenseError:
    print "3D Analyst license is unavailable"  
except arcpy. ExecuteError:
    print(arcpy.GetMessages(2))
finally:
    # Check in the 3D Analyst extension
    #
    arcpy.CheckInExtension("3D")

Выражение raise

Предыдущий пример иллюстрирует ошибку в исключении, которое возникло в коде В некоторых случаях может потребоваться создать пользовательские исключения. Для этой цели может быть использовано выражение raise. В следующем коде, выражение raise используется, когда входной класс пространственных объектов определяется как не содержащий объектов. Это не обязательно ошибка, но условие, при котором код может быть использован.

class NoFeatures(Exception):
    pass
import arcpy
import os
import sys
arcpy.env.overwriteOutput = True
fc = arcpy.GetParameterAsText(0)
try:
    # Check that the input has features
    #
    result = arcpy.GetCount_management(fc)
    if int(result[0]) > 0:
        arcpy.FeatureToPolygon_management(
            fc, os.path.join(os.path.dirname(fc), 'out_poly.shp'))
    else:
        # Raise custom exception
        #
        raise NoFeatures(result)
except NoFeatures:
    # The input has no features
    #
    print('{} has no features'. format(fc))
except:
    # By default any other errors will be caught here
    #
    e = sys.exc_info()[1]
    print(e.args[0])

Класс ExecuteError

Если выполнение инструмента геообработки прерывается, то появляется класс исключений arcpy.ExecuteError, это означает, что вы можете разделить ошибки на различные группы, ошибки геообработки (они вызывают исключение arcpy.ExecuteError) и другие типы ошибок. Затем можно обрабатывать эти ошибки по разному, как показано в следующем коде:

import arcpy
import sys
try:
    result = arcpy.GetCount_management("C:/invalid.shp")
  
# Return geoprocessing specific errors
#
except arcpy.ExecuteError:    
    arcpy.AddError(arcpy.GetMessages(2))    
# Return any other type of error
except:
    # By default any other errors will be caught here
    #
    e = sys.exc_info()[1]
    print(e.args[0])

traceback

В больших и более сложных скриптах бывает сложно точное определить место возникновения ошибки. Модули Python sys и traceback могут быть использованы вместе для определения точного расположения и причины появления ошибки, определения самой ошибки более точным образом и экономят время при отладке скрипта.

# Import the required modules
#
import arcpy
import sys
import traceback
arcpy.env.workspace = "C:/Data/myData.gdb"
try:
    arcpy.CreateSpatialReference_management()
    #--------------------------
    # Your code goes here
    #
    # See the table below for examples
    #--------------------------
except arcpy.ExecuteError: 
    # Get the tool error messages 
    # 
    msgs = arcpy.GetMessages(2) 
    # Return tool error messages for use with a script tool 
    #
    arcpy.AddError(msgs) 
    # Print tool error messages for use in Python/PythonWin 
    # 
    print(msgs)
except:
    # Get the traceback object
    #
    tb = sys.exc_info()[2]
    tbinfo = traceback.format_tb(tb)[0]
    # Concatenate information together concerning the error into a message string
    #
    pymsg = "PYTHON ERRORS:\nTraceback info:\n" + tbinfo + "\nError Info:\n" + str(sys. exc_info()[1])
    msgs = "ArcPy ERRORS:\n" + arcpy.GetMessages(2) + "\n"
    # Return python error messages for use in script tool or Python Window
    #
    arcpy.AddError(pymsg)
    arcpy.AddError(msgs)
    # Print Python error messages for use in Python / Python Window
    #
    print(pymsg)
    print(msgs)

Если вышеуказанный код будет использован, и в нем возникнет ошибка геообработки, такая как некорректные входные данные, это вызовет arcpy.ExecuteError, и будет использовано первое выражение except. Это выражение выведет сообщение об ошибке с помощью функции GetMessages. Если в коде возникнет ошибка другого типа, будет использовано второе выражение except. Вместо вывода сообщения о процессе геообработки, будет получен объект traceback и выведено подходящее сообщение о соответствующей системной ошибке.

В таблице ниже показаны ожидаемые ошибки, являющиеся результатом трех различных строк кода, который мог быть использован вместо вышеуказанного кода. Первый пример – ошибка инструмента геообработки, которая генерирует информацию traceback и сообщения об ошибках геообработки. Второй и третий примеры не обрабатываются, а происходит только генерация данных traceback.

PYTHON ERRORS:
Traceback info:
  File "c:\temp\errortest.py", line 10, in <module>
    arcpy.GetCount_management("")
Error Info:
Failed to execute. Parameters are not valid.
ERROR 000735: Input Rows: value is required
Failed to execute (GetCount).
ArcPy ERRORS:
Failed to execute. Parameters are not valid.
ERROR 000735: Input Rows: value is required
Failed to execute (GetCount).

PYTHON ERRORS:
Traceback info:
  File "c:\temp\errortest.py", line 10, in <module>
    x = "a" + 1
Error Info:
cannot concatenate 'str' and 'int' objects

PYTHON ERRORS:
Traceback info:
  File "c:\temp\errortest. py", line 10, in <module>
    float("a text string")
Error Info:
invalid literal for float(): a text string

Получение сообщений об ошибках от объекта Result

Краткая информация об объекте Result, показанном ниже:

result = arcpy.GetCount_management("c:/data/rivers.shp")

Если при вызове GetCount_management выдается исключение, объект Result не создается. Это означает, что вы не сможете получать сообщения об ошибках от объекта Result.

import arcpy
try:
    result = arcpy.GetCount_management("c:/data/rivers.shp")
# Return Geoprocessing specific errors
# (this method is incorrect!)
except arcpy.ExecuteError:
    arcpy.AddError(result.getMessages(2))

Выполнение представленного выше кода прерывается с сообщением name ‘result’ is not defined. Это связано с тем, что объект Result не создается из-за ошибки инструмента. Поскольку объект Result не создается, при попытке использования метода getMessages возникает ошибка Python.

Примечание:

Объект Result, создаваемый посредством службы геообработки в ArcGIS for Server, создается даже при ошибке инструмента. Объект Result не создается только тогда, когда инструмент запускается локально и выдает ошибку. Более подробную информацию об использовании объекта result смотрите в разделе Получение результатов инструмента геообработки.

Связанные разделы

Без ошибок и опечаток | Мир ПК

Основная идея

За счет чего это можно сделать? Некоторые ошибки (назовем их «хорошими») допустимо исправлять автоматической заменой ошибочного слова на правильное, например: «собераюсь» ‡ «собираюсь». Однако далеко не все ошибки таковы. Предположим, неправильно написано «садится» вместо «садиться» — оба эти слова есть в русском языке, поэтому автоматически заменять одно на другое нельзя. Или, скажем, «оптека» — непонятно, что же должно быть на самом деле, то ли «оптика», то ли «аптека».

Так вот, если написать программу, исправляющую хотя бы наиболее распространенные «хорошие» ошибки, то объем ручной работы заметно сократится. Ведь чтобы исправить одну ошибку вручную, нужно выполнить целую последовательность действий, например: подвести курсор к нужному месту текста, удалить неправильный или лишний символ и/или вставить правильный. Бывают ошибки и в двух символах, переставленных местами, и еще более сложные. Особенно полезной такая программа будет при обработке текстов с большим количеством ошибок.

Разумеется, если в тексте с какой-то целью присутствуют слова, специально написанные неправильно (как, например, в этой статье), то нужно либо отказаться от автоисправления ошибок, либо получившийся после него текст сравнить с исходным, проверяя, не произошло ли ненужных исправлений.

Первые шаги

Для начала я написал простейшую программу на Perl (этот язык весьма удобен для работы с текстами), которая читала исходный текстовый файл, исправляла часть ошибок с помощью замен неправильных слов на правильные и записывала результат. Для простоты я решил ограничиться обработкой таких текстовых файлов, где не используются переносы слов.

Участок программы, исправляющий ошибки, представлял собой последовательность операторов поиска-замены следующего вида:

Здесь конструкция «(?

Чтобы программа была эффективной, она должна исправлять как можно больше ошибок. А значит, нужно было добавлять в нее операторы для исправления новых ошибок. Я это делал прямо в процессе редактирования текста. Дабы меньше отвлекаться от этой своей основной задачи, я, исправив очередную «хорошую» ошибку, добавлял оператор для ее исправления, только если она встречалась достаточно часто.

Следующим шагом было некоторое упрощение добавления информации для исправления ошибок. Я изменил программу так, чтобы пары из неправильного и правильного слов содержались не непосредственно в операторах поиска-замены, а в отдельном файле-словаре в виде «неправильное слово ‡ правильное слово». Программа читала содержимое этого словаря и в соответствии с ним выполняла замены. Добавить новую пару в словарь было несколько проще, чем добавить новый оператор поиска-замены в программу.

Хотелось бы, однако, пополнять словарь так, чтобы вовсе не приходилось отвлекаться от редактирования текста. Например, сначала отредактировать текст, а потом, в удобное время, сравнить исходный текст с отредактированным, находя исправленные слова и добавляя в словарь «хорошие» пары слов (т. е. соответствующие «хорошим» ошибкам). Но это процесс трудоемкий, и выполняя его вручную, легко что-нибудь пропустить.

Автоматизация пополнения словаря

К счастью, возникла идея почти полной автоматизации этого процесса. Пусть специальная программа сравнивает исходный текст с отредактированным, находя исправленные слова. Найденные пары слов (слово с ошибкой и исправленный вариант) она будет предъявлять пользователю, который и вынесет вердикт: является ли данная пара «хорошей» или нет. «Хорошие» пары программа добавит к словарю.

То есть тут человек берет на себя именно ту часть работы, которую компьютеру выполнить затруднительно: оценивает, является ли очередная пара слов «хорошей». А все остальное делается автоматически.

Руководствуясь вышеизложенным, предстояло разработать алгоритм и написать требуемую программу для пополнения словаря.

О разработке алгоритма создания и дополнения словаря, написании соответствующей программы и работе с ней вы можете прочесть в полной версии статьи на “Мир ПК-диске».

В Microsoft Word появилась функция «Корректор», которая исправляет стилистические ошибки в тексте с помощью искусственного интеллекта

Компания Microsoft сообщила, что в новой версии текстового редактора Microsoft Word из пакета Office 365 появилась панель «Корректор», в работе которой применяются технологии искусственного интеллекта, что позволяет не только исправлять грамматические ошибки, но и давать рекомендации пользователям по улучшению стилистики текста.

Панель «Корректор» работает подобно привычной функции «Правописание», исправляющей орфографические и пунктуационные ошибки, а также отображает список предложений по улучшению стиля. К примеру, слова maybe и basically («может быть» и «в основном») будут помечены как вносящие неуверенность в том случае, если их можно удалить без потери смысла. Слово really («действительно») будет отмечено, если встретится в составе выражения вроде «действительно хорош» — в таком случае лучше написать просто «хорош», и Word на это укажет. Но если автор задает вопрос «Действительно?», то программа поймет, что без этого слова не обойтись и не будет предлагать правку.

Панель «Корректор» пришла на смену стандартной панели проверки орфографии и вызывается так же — по нажатию на F7 или из контекстного меню к подчеркнутому слову. Потенциальные грамматические ошибки Word подчеркивает двойной синей линией, а стилистические недочеты — желтым пунктиром. Помимо предложений по замене слов, в «Корректоре» для наглядности целиком приводятся проблемные предложения, а также сопутствующие правила грамматики и пунктуации. Первыми доступ к новой функции получили участники программы Office Insider, панель «Корректор» доступна в Word из Office 365 начиная с версии 16.0.7409.1000.

«Слова, без которых можно обойтись, неясные выражения, пассивный залог, жаргонизмы, — все это огрехи, которыми нередко изобилуют даже грамотно написанные тексты. Подтянуть стилистику помогает тренировка под руководством опытного редактора, который укажет на все недостатки и попросит поправить. С недавних пор роль такого наставника может взять на себя искусственный интеллект, а точнее — привычный Microsoft Word.» — отметили в Microsoft.

Напомним, что разработчики Office и других продуктов Microsoft в последнее время активно внедряют функции, в основе которых лежат интеллектуальные алгоритмы: в 2014 году в Skype появился машинный перевод речи на лету, основанный на технологии глубоких нейросетей, а в 2016 году в Office добавили функцию «Интеллектуальный поиск», которая находит словарные определения и энциклопедические справки.

Источник: Microsoft

Руководство программиста по теории — Исправление ошибок

Страница 1 из 2

Коды с исправлением ошибок необходимы для вычислений и всех видов связи. Сначала они кажутся немного волшебными. Как можно не только обнаружить ошибку, но и исправить ее? Как они работают? На самом деле, оказывается, очень легко понять более глубокие принципы.

Это отрывок из моей недавней книги по теории:

Теперь доступен в мягкой обложке и в электронной книге на Amazon.

Содержание

1. Что такое информатика?
   Часть I Что вычислимо?
2. Что такое вычисления?
3. Проблема остановки
4. Конечные автоматы
5. Практическая грамматика
6. Числа, бесконечность и вычисление
   Извлечение 1: Числа
   Извлечение 2: Алеф Ноль Первый трансфинит
   Извлечение 3: В поисках Алеф-Один *** НОВИНКА!
   
7. Колмогоровская сложность и случайность
   Выдержка 1: Колмогоровская сложность
8. Алгоритм выбора
9. Теорема Гёделя о неполноте
10. Лямбда-исчисление
    Часть II Биты, коды и логика
11. Теория информации
12. Теория кодирования — Разделение бита
13. Исправление ошибок
14. Логическая логика
    Вычислительная сложность, часть III
15. Насколько это может быть сложно?
16. Отрывок 1: Откуда берутся большие проблемы
17. Рекурсия
    Извлечение 1: Почему Рекурсия
18. NP против алгоритмов P
    Выдержка 1: NP и Co-NP
19. Выписка 2: NP Complete

Коды с исправлением ошибок необходимы для вычислений и связи. Сначала они кажутся чем-то вроде волшебства — как можно не только обнаружить ошибку, но и исправить ее? На самом деле, оказывается, очень легко понять более глубокие принципы.

Обнаружение и исправление ошибок — фундаментальное приложение теории кодирования. Без современных кодов исправления ошибок звуковой компакт-диск никогда бы не работал. Из-за неизбежных ошибок при чтении диска на нем было бы так много щелчков, щелчков и пропущенных битов, что вы просто не смогли бы его прослушать.Фотографии, отправленные с космического корабля, не были бы жизнеспособными без кодов исправления ошибок. Серверы часто используют модули памяти ECC, где ECC означает код исправления ошибок, и безопасное хранение данных не было бы безопасным без использования ECC. Наконец, всеми любимый QR-код имеет четыре возможных уровня исправления ошибок, самый высокий уровень допускает повреждение до 30% кода:

Этот QR-код все еще можно прочитать — это ссылка на Википедию — из-за ошибки исправления кодов Рида-Соломона.

Итак, как работает обнаружение и исправление ошибок?

Ошибка четности

Есть классическая шутка программистов, которую вы, наверное, уже слышали:

Программист покупает попугая. Попугай сидит на плече программиста и говорит «штук девять, штук девять…». Когда его спрашивают, почему не говорят традиционные «кусочки по восемь», программист отвечает: «Это ошибка попугая!»

Проверка ошибок четности была первым кодом обнаружения ошибок, и он используется до сих пор.Его преимущество в том, что его легко понять и легко реализовать. Его также можно расширить до более совершенных кодов обнаружения и исправления ошибок.

Чтобы понять, как работает проверка четности, рассмотрим семибитный элемент данных:

0010010

Если это было сохранено каким-то небезопасным образом, то если бы один бит был изменен с 0 на 1 или наоборот, вы никогда не узнаете. Если, однако, вместо восьми битов мы сохраняем девять, причем девятый — бит четности — установлен так, чтобы общее количество единиц было четным или нечетным, вы можете увидеть, что изменение одного бита можно обнаружить.

Если вы выберете нечетную четность, тогда восемь битов будут:

1 0010010

, то есть бит четности — это 1 , и если какой-либо из битов изменится, то четность изменится с нечетной на четную, и вы знаете, что произошла битовая ошибка.

Проверка четности обнаруживает ошибку в одном бите, но пропускает любые ошибки, которые меняют два бита, потому что после любого четного числа смен битов четность остается прежней.

Этот тип проверки ошибок используется, когда существует довольно малая вероятность изменения одного бита и, следовательно, еще меньшая вероятность изменения двух битов.

Расстояние Хэмминга

Когда вы впервые встречаетесь с обнаружением ошибок четности, все кажется очень простым, но это кажется «разовым», а не общим принципом. Как, например, вы можете расширить его для обнаружения двух- или трехбитной ошибки? Фактически, проверка четности — это простейший случай очень общего принципа, но вы должны подумать обо всем этом немного по-другому, чтобы понять это.

Когда бит изменяется случайным образом из-за шума, вы можете думать о слове данных как о перемещенном на небольшое расстояние от своего истинного местоположения.Однобитное изменение перемещает его на крошечную величину, двухбитное изменение перемещает его дальше и так далее. Чем больше битов изменено, тем дальше слово данных находится от своего исходного истинного местоположения. Простая мера этого расстояния между двумя словами данных — подсчитать количество битов, на которые они различаются. Например, два слова данных 011 и 110 разделены на две единицы, потому что они различаются в двух местах — первом и последнем битах. Это расстояние называется расстоянием Хэмминга в честь Р. У. Хэмминга, который провел большую часть первых работ по обнаружению и исправлению ошибок.

Ричард Хэмминг 1915–1998

Какое отношение имеет расстояние Хэмминга к проверке четности? Просто — если вы возьмете допустимое слово данных, с которым связан бит четности, и измените один бит, то у вас будет слово данных, которое находится на расстоянии одной единицы Хэмминга от оригинала. Каждое допустимое кодовое слово имеет недопустимое кодовое слово на расстоянии одной единицы от него.

Чтобы представить это, проще представить трехбитный код.В этом случае вы можете нарисовать куб, чтобы представить расположение каждого возможного кодового слова.

Кубик кода

Если мы будем рассматривать все слова четности как допустимые, а нечетные слова четности как недопустимые, вы сразу увидите, что такой код, как 000 , окружен недопустимыми кодами на расстоянии одной единицы, например 001 , 010 и 100 . Если вы отойдете на две единицы, вы снова получите действительные коды.Более того, каждый действительный код окружен кластером недействительных кодов на расстоянии одной единицы. Другими словами, однобитовая ошибка всегда перемещает действительный код в недопустимый, и, следовательно, мы обнаруживаем ошибку.

Красные углы — допустимые коды — черные — недопустимые

52>

Кодирование для обнаружения и исправления ошибок

Аннотация:

Помехи окружающей среды и физические дефекты в среде связи может вызвать случайные битовые ошибки во время передачи данных. Кодирование ошибок — это метод обнаружения и исправления этих ошибок для обеспечения передачи информации неповрежденным от источника до места назначения. Кодирование ошибок используется для обозначения неисправности. терпимые вычисления в компьютерной памяти, магнитных и оптических носителях данных, спутниковая и дальняя космическая связь, сетевая связь, сотовая связь телефонные сети и практически любые другие формы передачи цифровых данных.Кодирование ошибок использует математические формулы для кодирования битов данных в источнике в более длинные битовые слова для передачи. Тогда «кодовое слово» может быть декодируется в месте назначения для получения информации. Дополнительные биты в кодовое слово обеспечивает избыточность, которая, в соответствии с используемой схемой кодирования, будет разрешить получателю использовать процесс декодирования, чтобы определить, среда связи привела к ошибкам и в некоторых случаях исправила их так, чтобы данные не нужно повторно передавать.Выбраны разные схемы кодирования ошибок. в зависимости от типов ожидаемых ошибок, ожидаемая среда передачи данных частота ошибок и возможность повторной передачи данных. Быстрее процессоры и более совершенные коммуникационные технологии делают кодирование более сложным схемы, с лучшими возможностями обнаружения и исправления ошибок, возможно для встроенные системы меньшего размера, обеспечивающие более надежную связь. Тем не мение, компромиссы между полосой пропускания и накладными расходами на кодирование, сложностью кодирования и допустимая задержка кодирования между передачами должна учитываться для каждого заявление.

Состав:

Введение

Кодирование ошибок — это метод обеспечения надежной передачи цифровых данных и хранение, когда используемый носитель связи имеет недопустимую частоту ошибок по битам (BER) и низкое отношение сигнал / шум (SNR). Кодирование ошибок используется во многих цифровые приложения, такие как компьютерная память, магнитные и оптические хранилища данных СМИ, спутниковая связь и связь в дальнем космосе, сетевая связь и сотовые телефонные сети.Вместо того, чтобы передавать цифровые данные в виде необработанного бита для битовой формы данные кодируются дополнительными битами в источнике. Чем дольше Затем передается «кодовое слово», и получатель может его декодировать, чтобы получить желаемую информацию. Дополнительные биты преобразуют данные в допустимое кодовое слово в схеме кодирования. Пространство допустимых кодовых слов меньше чем пространство возможных битовых строк такой длины, поэтому пункт назначения может распознать недопустимые кодовые слова. На рисунке 1 показан код. пространство слова.

Если во время передачи появляются ошибки, они, скорее всего, будут обнаружены. во время процесса декодирования в месте назначения, потому что кодовое слово будет преобразован в недопустимую битовую строку. Учитывая передаваемую строку данных длиной k бит, существует 2 ^k возможных битовых строк, которые данные может быть. Кодирование ошибок предполагает наихудший сценарий, когда информация закодированная может быть любой из этих битовых строк. Следовательно, будет 2 ^k допустимые кодовые слова.Кодовые слова будут иметь длину n бит, где n> k. Так что просто наличие лишних битов при передаче данных устраняет многие из возможных 2 ⁿ битовых строк как допустимые кодовые слова.

Возможно, самый простой пример кодирования ошибок — это добавление бита проверки четности. А битовая строка, которая должна быть передана, имеет один бит, связанный с ней, чтобы создать код слово для передачи. Бит равен 1 или 0 в зависимости от четности. Если нечетное используется четность, бит четности будет добавлен таким образом, чтобы сумма единиц в кодовое слово нечетное.Если используется четность, сумма единиц в коде слово должно быть четным. Это проиллюстрировано в 3-битном примере на Рисунке 2 ниже.

Здесь мы хотим отправить два бита информации и использовать один бит проверки четности всего для трехбитовых кодовых слов. Данные могут быть четырьмя возможными битами комбинаций, поэтому пространство кодового слова составляет четыре из восьми возможных 3-битных струны. Здесь мы используем нечетную четность. Когда данные передаются с использованием этого схема кодирования, любые битовые строки с четностью будут отклонены, потому что они не являются допустимыми кодовыми словами.Эта простая схема кодирования ограничена, потому что она может обнаруживает только нечетное количество битовых ошибок в исходных данных и не имеет возможности исправления ошибок. Есть много других методов кодирования ошибок. которые обеспечивают лучшую защиту за счет увеличения пропускной способности и сложность.

Ключевые понятия

Возможности конкретного кодирования по обнаружению и исправлению ошибок. схема соотносится с ее кодовой скоростью и сложностью.Кодовая скорость — это отношение битов данных к общему количеству битов, переданных в кодовых словах. Высокий код Скорость означает, что информационное содержание высокое, а накладные расходы на кодирование низкие. Тем не менее чем меньше битов используется для избыточности кодирования, тем меньше защита от ошибок. А необходимо найти компромисс между доступностью полосы пропускания и количеством ошибок защита, необходимая для связи.

Теорема Шеннона

Методы кодирования ошибок основаны на теории кодирования информации, области разработан на основе работы Клода Шеннона.В 1948 году Шеннон представил теория, которая гласит: учитывая код с кодовой скоростью R, которая меньше, чем пропускная способность канала связи C, код существует, для длины блока n бит, с кодовой скоростью R, которая может передаваться по каналу с произвольной малая вероятность ошибки. Теоретически мы должны быть в состоянии разработать схема кодирования для конкретного канала связи для любой частоты ошибок, но не удалось разработать код, удовлетворяющий теореме Шеннона [Wells99].Это означало бы, что есть еще предстоит проделать большую работу по совершенствованию методов кодирования ошибок. Криптография, метод шифрования данных в целях безопасности, а не надежности, также является потомок работы Шеннона.

Компромиссы

При выборе схемы кодирования для защиты от ошибок типы ошибок, которые необходимо учитывать, как правило, происходящие на канале связи. Есть два типы ошибок, которые могут возникнуть в канале связи: случайные битовые ошибки и пакетные ошибки.Канал, который обычно имеет случайные битовые ошибки, будет иметь тенденцию имеют изолированные перевороты битов во время передачи данных, а битовые ошибки независимы друг от друга. Канал с пакетными ошибками будет иметь сгущения. битовых ошибок, возникающих во время одной передачи. Коды ошибок были разработан специально для защиты как от случайных битовых ошибок, так и от пакетов ошибки.

Системы реального времени должны учитывать компромисс между задержкой кодирования и ошибкой защита.Схема кодирования с высокими возможностями исправления ошибок потребует дольше декодировать и будет недетерминированным. Это могло вызвать пропущенный крайний срок и отказ, если часть необходимой информации застряла при декодировании.

Во встроенных системах кодирование ошибок особенно важно, потому что может использоваться в критических приложениях и не допускает ошибок. Схемы кодирования становятся все более сложными и вероятностными, что делает реализацию кодеры и декодеры в программном обеспечении привлекательны.Поскольку вычислительная мощность относительно быстрое и дешевое программное обеспечение более осуществимо. Однако программное обеспечение гораздо более подвержен конструктивным дефектам и ошибкам, что делает алгоритм кодирования менее надежный. Усложнение программного обеспечения вносит больше ошибок в дизайн и реализация.

Доступные инструменты, методы и показатели

Существует два основных типа схем кодирования: линейные блочные коды и сверточные коды. Линейные блочные коды характеризуются сегментацией сообщение на отдельные блоки фиксированной длины и кодирование каждого блока по одному в время для передачи.Сверточные коды кодируют весь поток данных в одно длинное кодовое слово и передавать его по частям.

Линейные блочные коды

Линейные блочные коды названы так, потому что каждое кодовое слово в наборе является линейная комбинация набора кодовых слов генератора. Если сообщения k бит long, а кодовые слова имеют длину n бит (где n> k), имеется k линейно независимые кодовые слова длины n, образующие порождающую матрицу. Чтобы закодировать любой сообщение из k бит, вы просто умножаете вектор сообщения u на генератор матрица для создания вектора v кодового слова длиной n бит [Lin83].

Линейные блочные коды очень легко реализовать аппаратно, и поскольку они алгебраически определены, они могут быть декодированы за постоянное время. Они имеют очень высокие кодовые скорости, обычно выше 0,95. У них низкие накладные расходы на кодирование, но у них ограниченные возможности исправления ошибок. Они очень полезны в ситуации, когда BER канала относительно низок, полоса пропускания доступность ограничена при передаче, и данные легко повторно передать.

Один класс линейных блочных кодов, используемых для высокоскоростной компьютерной памяти: Коды SEC / DED (исправление одиночной ошибки / обнаружение двойной ошибки).На высокой скорости память, полоса пропускания ограничена из-за относительно высокой стоимости за бит по сравнению с низкоскоростной памятью вроде дисков [Costello98]. Частота ошибок обычно невелика и, как правило, происходит побайтово, поэтому SEC / DED схема кодирования для каждого байта обеспечивает достаточную защиту от ошибок. Кодирование ошибок в этой ситуации должен быть быстрым, потому что желательна высокая пропускная способность. SEC / DED коды чрезвычайно просты и не вызывают большой задержки кодирования.

Коды CRC

Cyclic Redundancy Check (CRC) являются специальным подмножеством линейного блока. коды, которые очень популярны в цифровых коммуникациях.Коды CRC имеют свойство циклического сдвига; когда любое кодовое слово поворачивается влево или вправо любым количество битовых цифр, результирующая строка по-прежнему является словом в кодовом пространстве [Wells99]. Это свойство делает кодирование и декодирование очень легко и эффективно реализовать с помощью простых регистров сдвига. Главный недостатком использования кодов CRC является то, что они имеют только обнаружение ошибок возможности. Они не могут исправить какие-либо ошибки в данных, обнаруженные на место назначения, и данные должны быть переданы снова, чтобы получить сообщение. По этой причине коды CRC обычно используются вместе с другим кодом. что обеспечивает исправление ошибок. Если коды CRC — единственные, которые используются для приложения, необработанный BER канала обычно чрезвычайно низок, а данные не критично по времени. Они хороши для магнитных и оптических накопителей, где возможен простой запрос на повторную передачу для исправления битовых ошибок.

Сверточные коды

Сверточные коды обычно сложнее линейных блочных кодов, сложнее в реализации и имеют более низкую кодовую скорость (обычно ниже 0.90), но обладают мощными возможностями исправления ошибок. Они популярны в спутниковых и связь в дальнем космосе, где пропускная способность практически неограничена, но BER намного выше, и повторные передачи невозможны.

Сверточные коды сложнее декодировать, потому что они закодированы с использованием конечных автоматов, которые имеют пути ветвления для кодирования каждого бита в последовательность данных. Известный процесс декодирования сверточных кодов быстро — это алгоритм Витерби. Алгоритм Витерби — это максимальная вероятность декодер, что означает, что выходное кодовое слово декодирования передачи всегда тот, с наибольшей вероятностью быть правильным словом передается из источника.

Связь с другими темами

Кодирование ошибок — это метод достижения отказоустойчивых вычислений, но он также имеет связывает встроенные коммуникации и факторы в проектировании надежных в реальном времени системы.

• Отказоустойчивые вычисления — Кодирование ошибок помогает переносить сбои, вызванные шумом в канале связи или бит ошибки в памяти или хранилище.
• Embedded Communications — Кодирование ошибок методы необходимы для надежной цифровой связи в любой сети.
• Системы реального времени — временные ограничения системы реального времени ограничивают выбор схем кодирования внутри системы и сколько защиты от ошибок можно включить при соблюдении сроков.
• Надежность программного обеспечения — ошибка реализации коды в программном обеспечении означают, что они должны быть такими же надежными, как и аппаратные реализации.
• I / O — Преобразование аналоговых сигналов от датчиков в из реального мира в цифровую информацию и передачу этой информации в система управления может вносить ошибки битового уровня, которые может предотвратить кодирование ошибок.

Выводы

Следующие идеи являются важными, чтобы вынести из чтения о в этой теме:

• Важными причинами использования кодирования являются обеспечение надежного хранения данных в лицо незначительного повреждения / потери данных и получение возможности обеспечить высокий точный ввод / вывод даже на зашумленных линиях передачи, таких как сотовые телефоны (ошибка кодирование отделяет точность сообщения от аналогового уровня шума).
• Методика кодирования ошибок для приложения должна быть выбрана на основе:

• Типы ошибок, ожидаемых в канале (например, пакетные ошибки или случайные битовая ошибка)
• Можно ли повторно передать информацию (коды для только обнаружение ошибок или обнаружение и исправление ошибок)
• Ожидаемая частота ошибок на канале связи (высокая или низкая)

• Есть несколько компромиссов между эффективностью канала и количеством реализована логика кодирования / декодирования:

• Схемы кодирования с более высокими возможностями обнаружения и исправления ошибок потребует больше накладных расходов и пропускной способности. Это приводит к снижению информации скорости передачи.
• Повышенная сложность кодирования для лучшего исправления ошибок приведет к увеличению задержки в источнике и назначении для кодирования и декодирования.
• Системы реального времени не допускают ошибок, но коды с непостоянными время задержки повлияет на временные графики.

• Лучшие схемы защиты от ошибок сложнее и реализуются в программном обеспечении. Однако это добавляет сложности и может быть менее надежным, чем аппаратные кодеры и декодеры, потому что программное обеспечение менее зрелое и более сложно проверить его правильность.

Аннотированный список ссылок

• [Costello98] Costello, Daniel J., Jr .; Хагенауэр, Иоахим; Имаи, Хидеки; Викер, Стивен Б., «Применение контроля ошибок» Кодирование ». IEEE Transactions of Information Theory , October 1998, т. 44, нет. 6, стр. 2531 — 2560.
  В этой статье дается обзор многих приложений кодирования ошибок и теория позади них.
• [Lin83] Линь Шу; Костелло, Дэниел Дж., Младший, ошибка Кодирование управления: основы и приложения . Энглвуд Клиффс, Нью-Джерси: Прентис-Холл, 1983.
• 
  Это исчерпывающая книга по основам теории и применению ошибок. кодирование. Все распространенные схемы кодирования от линейных блочных кодов до циклических кодов и обсуждаются сверточные коды. Это хорошая книга как для справки, так и для обучение.
  
• [Wells99] Wells, Ричард Б., Прикладное кодирование и Теория информации для инженеров .Река Аппер Сэдл, Нью-Джерси: Прентис-Холл, 1999.
• 
  В этой книге больше внимания уделяется кодированию приложений и реализаций. с меньшим вниманием к теории кодирования. Это хорошее стартовое руководство для инженеров. не обучен на уровне математики, необходимом для большинства схем кодирования.

Указатель других тем

Домашняя страница

Расшифровка кодов с исправлением ошибок посредством линейного программирования

Абстрактные

Описание

Отдел

Издатель

Массачусетский технологический институт

Ключевые слова

Электротехника и информатика.

— обзор

Введение

Конечные системы Вейля находят свое применение в различных областях квантовой теории информации. Они помогают обуздать рост сложности для большого класса квантовых систем: ключевое несоответствие между классическими и квантовыми системами — это разница в росте сложности при переходе к все большим и большим системам.С этим сталкиваются при моделировании квантовой спиновой системы на компьютере, например, с целью определения основного состояния твердотельной модели магнетизма. Для модели классических спинов N это включает проверку энергии для 2 ^N различных конфигураций, но для модели с квантовыми спинами это требует решения уравнения собственных значений в гильбертовом пространстве размерности 2 ^N , что значительно усложняет задачу для большого N .Для трехмерной решетки с тремя узлами в каждом направлении N = 27, это проблема в 10 ⁸ измерениях, а размер решетки 4 приводит к совершенно неразрешимым 10 ¹⁹ измерениям.

Поэтому очень желательно найти способы обработки хотя бы некоторых аспектов больших сложных квантовых систем без необходимости фактически записывать векторы состояния компонент за компонентом. Состояния, инвариантные относительно подходящей дискретной абелевой группы симметрий, удовлетворяют этому условию. Их можно охарактеризовать простыми комбинаторными данными, которые не растут экспоненциально с размером системы N .В то же время класс этих так называемых состояний стабилизатора достаточно сложен, чтобы уловить некоторые ключевые особенности, необходимые для вычислений, особенно квантовую корреляцию (запутанность) между подсистемами. Также было показано, что их достаточно для генерации больших кодов с квантовой коррекцией ошибок.

Еще одна мотивация для конечных систем Вейля напрямую основана на построении кодов с квантовой коррекцией ошибок из классических процедур кодирования ( см. Квантовая коррекция ошибок и отказоустойчивость).Используемая там техника «квантования» естественным образом приводит к структуре конечных систем Вейля.

Конечные системы Вейля точно представляют собой квантовые версии дискретных абелевых групп симметрии. Это стандартная процедура для построения квантовой версии группы симметрии путем соответствующего центрального расширения или, что эквивалентно, для изучения всех ее проективных представлений: композиция двух преобразований симметрии сохраняется только с точностью до фазы в гильбертовом пространстве представления. Унитарные операторы, представляющие преобразования симметрии, называются операторами Вейля.

Самый простой и наиболее яркий пример конечной системы Вейля — это три матрицы Паули и тождество. Эти четыре унитарных оператора создают проективное представление группы симметрии двоичных векторов (0, 0), (0, 1), (1, 0), (1, 1), где групповой закон является сложением по модулю два. Нулевой вектор (0, 0) соответствует идентичности, вектор (0, 1) присваивается X , (1, 0) соответствует Z , а (1, 1) отображается на i Y .Нетрудно проверить, что произведение двух операторов Паули сохраняет сложение двоичных векторов с точностью до фазы.

Дискретные системы Вейля глубоко связаны с симплектической геометрией векторных пространств над конечными полями. Аддитивная структура векторного пространства — это основная абелева группа симметрии. Обмен двумя операторами Вейля в продукте дает фазу, которая является экспонентой антисимметричной билинейной формы, как это объясняется в следующем разделе. Для неприводимых систем Вейля эта антисимметричная форма должна быть симплектической, поскольку операторы Вейля порождают полную матричную алгебру.В частности, для этого требуется, чтобы размерность лежащего в основе векторного пространства была четной. Матрицы Паули также являются примером этой более специальной структуры: двоичные векторы p, qp, q = 0,1 представляют собой двумерное векторное пространство над полем с двумя элементами {0, 1). Из коммутационных соотношений для операторов Паули следует, что симплектическая форма может быть вычислена для двух двоичных векторов (p, q), (p ′, q ′) согласно pq′ − qp′mod2. Очевидно, что двоичные векторы ( p, q ) следует интерпретировать как точки в дискретном фазовом пространстве, где первая запись соответствует импульсу, а вторая — положению.Ввиду этого дискретные системы Вейля служат конечномерным аналогом канонических коммутационных соотношений.

Для общей ситуации в квантовой теории информации неприводимая система Вейля представлена ​​в гильбертовом пространстве, описывая систему из нескольких отдельных частиц. Состояния стабилизатора остаются неизменными под действием так называемой изотропной подгруппы, которая состоит из взаимно коммутирующих операторов Вейля: этот вид инвариантности является именно тем типом ограничения, которое снижает сложность параметризации состояния.Для эффективного описания таких состояний доступны комбинаторные методы, например теория графов.

Операции, сохраняющие класс состояний стабилизатора (для определенной группы симметрии), должны быть ковариантными по отношению к этой симметрии. Эти операции называются каналами Клиффорда, которые имеют далеко идущие приложения в теории квантовой коррекции ошибок. Они также позволяют взять классические процедуры кодирования и превратить их в квантовые коды: на классическом уровне операция кодирования действует в классическом фазовом пространстве как линейное отображение (аддитивный код).С точностью до выбора фаз это создает квантовый канал, сохраняющий структуру систем Вейля. Эти коды называются кодами стабилизаторов и были исследованы многими авторами (Calderbank et al. 1997, Cleve and Gottesman 1996, 1997) ( см. Quantum Error Correction and Fault Tolerance). В частности, к этому классу принадлежат первые коды с квантовой коррекцией ошибок.

Эта статья организована следующим образом. В следующем разделе представлены основные математические понятия, такие как проективные представления, системы Вейля и неприводимость.Кроме того, представлены утверждения об основной структуре систем Вейля. Далее вводится понятие ковариантных каналов Вейля (каналов Клиффорда) и излагаются их основные свойства. В частности, приведены более сильные результаты для обратимого случая. Объясняется связь между симплектической геометрией и обратимыми операциями Клиффорда над конечными системами Вейля. Результаты об общей структуре состояний стабилизатора и кодах стабилизатора приведены в предпоследнем разделе. Наконец, описывается представление кодов стабилизатора в терминах графов.

Страница кодов исправления ошибок (ECC)

Добро пожаловать!

1. С. Лин и Д. Дж. Костелло младший, Кодирование с контролем ошибок: основы и приложения, , второе издание, Prentice Hall: Englewood Cliffs, NJ, 2004.
2. W.W. Петерсон и E.J. Велдон младший, Коды исправления ошибок , 2-е издание, Массачусетский технологический институт Издательство: Кембридж, Массачусетс, 1972.
3. Ф.Дж. Мак-Вильямс и N.J.A. Sloane, Теория кодов с исправлением ошибок , Северная Голландия: Нью-Йорк, штат Нью-Йорк, 1977.

Мой Учебник, теперь во втором издании, предлагает нежный и практический (с сопутствующий веб-сайт, содержащий больше программ C и Matlab) введение к основные принципы и применение кодов исправления ошибок:

Авторские права (c) 1996-2008. Роберт Морелос-Сарагоса.Все права защищены.

1. Вездесущий Коды Рида-Соломона

Барри А. Cipra, перепечатано из SIAM News, том 26-1, январь 1993 г.

2. Коды Рида-Соломона (RS)

Расшифровка Алгоритм Берлекампа-Масси (BM) с оценкой ошибок, как описано в Книга Лина и Костелло.
(Саймон Роклифф, 1989)

3. Рид-Соломон декодер ошибок и стираний

На основе вышеуказанная программа для обработки ошибок и стирания, а также другие функции.м), m <8 ... это дает хорошие идеи.
(Тирумурти, 1995)

4. Другой Декодер ошибок и стираний Рида-Соломона

Красиво написано, очень улучшенная версия программы выше. Теперь он позволяет пользователю создавать несколько энкодеры во время выполнения с указанными параметрами. Вы можете получить самую последнюю пакет здесь. Проверять также домашняя страница Фила.
(Фил Карн, 2006).

5. Коды BCH

Введите только длина и возможность исправления ошибок.Программа вычисляет генераторный полином любого двоичного кода BCH, плюс кодирование и декодирование используя алгоритм BM.
(Морелос-Сарагоса, 1994).

6. Двоичный (48,36,5) код BCH.

Этот код BCH используется в каналах управления для сотовой TDMA в США. код имеет возможность исправления только двух ошибок, быстрое декодирование осуществляется предварительное решение системы двух уравнений (синдромов) с двумя неизвестными (ошибочные позиции), см. книгу Мак-Вильямса и Слоуна, глава 3.ПРИМЕЧАНИЕ: В этой программе была «ошибка», исправленная 27.08.97.
(Морелос-Сарагоса, 1994).

7. Двоичный (31,21,5) код BCH.

Этот код BCH используется в спецификации протокола POCSAG для пейджеров. Программа идентичен приведенному выше, за исключением параметров. ПРИМЕЧАНИЕ: был «ошибка» в этой программе. Это было исправлено 27.08.97.
(Морелос-Сарагоса, 1997).

8. Голай (23,12,7) код

Быстрое кодирование и декодирование программным обеспечением с помощью справочных таблиц.Программа использует Таблица кодирования 16K на 16 бит и таблица декодирования 8K на 32 бит.
(Морелос-Сарагоса, 1994).

9. Код Гоппа

Кодирование / декодирование кода (1024,654,75) Goppa (изначально написанного с открытым ключом криптографическая схема). Эта программа представляет собой компактную реализацию кодов Гоппа с параметрами m = 10, t = 37 для 32-битных машин. Расшифровка метод Н. Паттерсона, « Алгебраическое декодирование кодов Гоппы », IEEE Пер.Инфо-теория , 21 (1975), 203-207.
(Аноним, насколько мне известно)

10. CRC-32

Вычисляет Значение CRC файла, используемое в ZMODEM или PKZIP.
(Крейг Брюс, 1994)

11. ecc-1.2.1.tar (106496 байт)

Подпрограммы для кодировать и декодировать файл с помощью кода RS (255,249,7).
(Пол Флаэрти, 1993)

12. Турбокоды. домашняя страница в JPL
13. декодер ТУРБО архив: BCJR_turbo.деготь

An реализация алгоритма BCJR, основанного на псевдокоде в Учебная статья У. Э. Райана (PS файл).
(Мэтис Уолма, 1998)

14. Расшифровка Витерби

Пакет viterbi-3.0.1.tar содержит программы для реализации декодирования Витерби (стандарт де-факто) скорость-1/2 и скорость-1/3 m = 7 сверточных кодов. Пакет simd-viterbi-2.0.1.tar содержит программы для реализации декодеров Витерби для r = 1/2 k = 7 и k = 9 кодов, которые используют наборы инструкций Intel / AMD SIMD (MMX / SSE / SSE2).Проверьте также Phil’s домашняя страница.
(Фил Карн, 2006)

15. galois.tar

Кодирование / декодирование для кодов BCH / RS.
(Барт Де Канн, 1994)

16. Модуляция QPSK с блочным кодированием для неравной защиты от ошибок (UEP)

Эта программа был использован для моделирования производительности схемы кодирования, предложенной в моем Кандидат наук. дипломная работа для UEP по каналу AWGN. Подробнее см .: R.H. Морелос-Сарагоса, С. Лин, « Коды блочной модуляции QPSK для неравных Защита от ошибок », Транзакции IEEE по теории информации , Vol.41, No. 2, pp. 576-581, March 1995.
(Morelos-Zaragoza, 1993)

17. Линейная граница кода

Насколько хорош код? Каковы нижняя и верхняя границы минимального расстояния линейный блочный код с учетом его длины и размера? Ответ на это вопрос можно найти он-лайн! ([email protected], 1995). Также попробуйте: http://www.codetables.de/ поддерживается Маркусом Грасслом (спасибо Axel Kohnert за указатель).


18. Устранение стирания коды

An реализация блочного кода для исправления стирания в сети протоколы связи.Кодер / декодер работает довольно быстро (до несколько МБ / с на Pentium).
(Луиджи Риццо, 1996)

19. конечный Калькулятор поля и симулятор Рида-Соломона

Java-апплет Калькулятор GF и кодировщик / декодер RS
(Эмина Солянин, 1997)

20. Windows 95 / NT программа для выполнения математики Поля Галуа

(Андрей Линь, 1997)

21. Свойства линейных двоичных кодов

Это C ++ программа (скомпилированная для Sparcs), вычисляющая свойства двоичных кодов, от более простых элементов, таких как минимальное расстояние и размер, до большего сложные свойства, такие как сложность декодирования решеток и граф Таннера кода не имеет циклов.
(Ари Трахтенберг, 1998)

22. Максимальная программа LFSR

Программа для найти примитивные полиномы максимальной длины цикла
(Стив Унгстад, 1999)

23. Учебник по Сверточное кодирование с декодированием Витерби

Цель это руководство познакомит читателя с упреждающим исправлением ошибок. метод, известный как сверточное кодирование с декодированием Витерби. Более в частности, это руководство будет сосредоточено в первую очередь на Витерби сам алгоритм декодирования.м.

Несколько MATLAB процедуры для кодирования / декодирования кодов проверки на четность низкой плотности.
(Игорь Козинцев, 1999)

Perl-скрипт для типа C2 алгебраический перемежитель.

Создает последовательность различных чисел такая, что длина последовательности может — любая степень двойки. Определенная характеристика порожденного последовательность состоит в том, что она симметрична в том смысле, что запись j в строке i означает, что запись в строке j равна i. (Перемежитель и деинтерливер идентичны!)
(Оскар Такешита, 1997)

Ошибка пересылки Коррекция (FEC) Страница

Этот сайт содержит несколько примеров программного обеспечения прямого исправления ошибок (FEC) и аппаратное обеспечение.Вы найдете примеры программного и аппаратного обеспечения бесплатно скачать, которые доступны как исходный код ‘C’, исходный код VHDL или как генераторы кода VHDL для SUN / Solaris.
(Кристиан Шулер, 1998. Обновлено в 2001 г.)

Быстро и точно оптимизатор распределения степеней для ансамблей кода ldpc

Инструмент ldpcopt был разработан в Швейцарии для поиска оптимизированного LDPC. распределения степеней для различных каналов.
(Абдельазиз АМРАУИ, 2001 г.)

Tc_Ds_Analysis.exe

Окна программа для вычисления спектра расстояний турбокода и объединения привязан к BER. См. Файл read_me
(Seokhyun Yoon, 2002.)

Коды исправления и обнаружения ошибок

В этом руководстве мы узнаем о некоторых из наиболее часто используемых кодов исправления и обнаружения ошибок. Мы увидим ошибки в цифровой связи, различные типы ошибок, некоторые коды исправления ошибок и обнаружения, такие как четность, CRC, код Хэмминга и т. Д.

Введение

В цифровых системах аналоговые сигналы преобразуются в цифровую последовательность (в виде битов). Эта последовательность битов называется «потоком данных». Изменение положения отдельного бита также приводит к катастрофической (серьезной) ошибке в выводе данных. Практически во всех электронных устройствах мы находим ошибки и используем методы обнаружения и исправления ошибок, чтобы получить точный или приблизительный результат.

Что такое ошибка

Данные могут быть повреждены во время передачи (от источника к получателю).На него может повлиять внешний шум или другие физические недостатки. В этом случае входные данные не совпадают с полученными выходными данными. Эти несовпадающие данные называются «Ошибка».

Ошибки данных приведут к потере важных / защищенных данных. Даже одно изменение в данных может повлиять на производительность всей системы. Как правило, передача данных в цифровых системах осуществляется в форме «битовой передачи». В этом случае ошибка данных, вероятно, изменится в положениях 0 и 1.

В начало

Типы ошибок

В последовательности данных, если 1 изменяется на ноль или 0 изменяется на 1, это называется «битовой ошибкой».

Обычно существует 3 типа ошибок при передаче данных от передатчика к приемнику. Это

• Однобитовые ошибки

• Множественные битовые ошибки

• Пакетные ошибки

Однобитовые ошибки данных

Изменение одного бита во всей последовательности данных называется «Однобитовой ошибкой». В системах последовательной связи очень редко возникает ошибка одного бита. Этот тип ошибки возникает только в параллельной системе связи, поскольку данные передаются побитно в одной строке, есть вероятность, что эта одна линия будет зашумленной.

Множественные ошибки битовых данных

Если есть изменение в двух или более битах последовательности данных от передатчика к приемнику, это называется «Множественная битовая ошибка». Этот тип ошибки возникает как в сетях передачи данных последовательного, так и параллельного типа.

Пакетные ошибки

Изменение набора битов в последовательности данных называется «пакетной ошибкой». Пакетная ошибка рассчитывается от первого изменения бита до последнего изменения бита.

Здесь мы идентифицируем ошибку с четвертого по шестой бит.Числа между 4-м и 6-м битами также считаются ошибкой. Этот набор битов называется «пакетной ошибкой». Эти пакетные биты меняются от передатчика к приемнику, что может вызвать серьезную ошибку в последовательности данных. Ошибки этого типа возникают при последовательной связи, и их трудно устранить.

В начало

Коды обнаружения ошибок

В цифровой системе связи ошибки передаются от одной системы связи к другой вместе с данными. Если эти ошибки не обнаружены и не исправлены, данные будут потеряны.Для эффективной связи данные должны передаваться с высокой точностью. Этого можно достичь, сначала обнаружив ошибки, а затем исправив их.

Обнаружение ошибок — это процесс обнаружения ошибок, которые присутствуют в данных, передаваемых от передатчика к приемнику в системе связи. Мы используем некоторые коды избыточности для обнаружения этих ошибок, добавляя к данным, когда они передаются от источника (передатчика). Эти коды называются «кодами обнаружения ошибок».

Типы обнаружения ошибок

1. Проверка четности
2. Циклическая проверка избыточности (CRC)
3. Продольная проверка избыточности (LRC)
4. Контрольная сумма

Проверка четности

Бит четности означает только дополнительный бит, добавленный к данным на передатчике перед передачей данных.Перед добавлением бита четности в данных вычисляется количество единиц или нулей. На основе этого расчета данных к фактической информации / данным добавляется дополнительный бит. Добавление бита четности к данным приведет к изменению размера строки данных.

Это означает, что если у нас есть 8-битные данные, то после добавления бита четности к двоичной строке данных она станет 9-битной двоичной строкой данных.

Проверка четности также называется «Вертикальной проверкой избыточности (VRC)».

Существует два типа битов четности при обнаружении ошибок:

Четность

• Если данные имеют четное число единиц, бит четности равен 0.Пример: данные — 10000001 -> бит четности 0
• Нечетное количество единиц, бит четности — 1. Пример: данные — 10010001 -> бит четности 1

Нечетность

• Если данные имеют нечетное количество единиц, бит четности равен 0. Пример: данные — 10011101 -> бит четности 0
• Четное количество единиц, бит четности — 1. Пример: данные — 10010101 -> бит четности 1

ПРИМЕЧАНИЕ : Подсчет данных биты также будут включать бит четности.

Схема, которая добавляет бит четности к данным на передатчике, называется «Генератором четности».Биты четности передаются и проверяются на приемнике. Если биты четности, отправленные в передатчике, и биты четности, полученные в приемнике, не равны, то обнаруживается ошибка. Схема, которая проверяет четность на приемнике, называется «Проверка четности».

Сообщения с четностью и нечетностью

К началу

Циклический контроль избыточности (CRC)

Циклический код — это линейный (n, k) блочный код со свойством, что каждый циклический сдвиг кодового слова приводит к другим кодовым словом.Здесь k указывает длину сообщения в передатчике (количество информационных битов). n — общая длина сообщения после добавления контрольных битов. (фактические данные и контрольные биты). n, k — количество проверочных битов.
Коды, используемые для контроля циклическим избыточным кодом посредством обнаружения ошибок, известны как коды CRC (коды циклического контроля избыточности). Коды циклического контроля избыточности представляют собой сокращенные циклические коды. Эти типы кодов используются для обнаружения ошибок и кодирования. Их легко реализовать с помощью регистров сдвига с обратной связью.Вот почему они широко используются для обнаружения ошибок в цифровой связи. Коды CRC обеспечат эффективный и высокий уровень защиты.

Генерация кода CRC

В зависимости от желаемого количества битовых проверок мы добавим несколько нулей (0) к фактическим данным. Эта новая последовательность двоичных данных делится на новое слово длины n + 1, где n — количество добавляемых контрольных битов. Напоминание, полученное в результате этого деления по модулю 2, добавляется к битовой последовательности делимого, чтобы сформировать циклический код.Сгенерированное кодовое слово полностью делится на делитель, который используется при генерации кода. Это передается через передатчик.

Пример

На стороне приемника мы делим полученное кодовое слово с тем же делителем, чтобы получить фактическое кодовое слово. Для безошибочного приема данных напоминание равно 0. Если напоминание не равно нулю, это означает, что в полученном коде / последовательности данных есть ошибка. Вероятность обнаружения ошибки зависит от количества контрольных битов (n), используемых для построения циклического кода.Для однобитовых и двухбитовых ошибок вероятность составляет 100%.

Для пакета ошибок длиной n — 1 вероятность обнаружения ошибки составляет 100%.

Пакетная ошибка длиной, равной n + 1, вероятность обнаружения ошибки снижается до 1 — (1/2) ^n-1 .

Пакетная ошибка длиной больше n — 1, вероятность обнаружения ошибки составляет 1 — (1/2) ⁿ .

В начало

Проверка с продольной избыточностью

В методе с продольной избыточностью БЛОКИРОВКА битов организована в виде таблицы (по строкам и столбцам), и мы будем вычислять бит четности для каждого столбца отдельно.Набор этих битов четности также отправляется вместе с нашими исходными битами данных.

Продольная проверка избыточности — это побитовое вычисление четности, поскольку мы вычисляем четность каждого столбца индивидуально.

Этот метод может легко обнаружить пакетные ошибки и одиночные битовые ошибки, и он не может обнаружить 2-битные ошибки, возникшие в одном вертикальном срезе.

К началу

Контрольная сумма

Контрольные суммы аналогичны битам четности, за исключением того, что количество битов в суммах больше, чем четность, и результат всегда ограничен равным нулю.Это означает, что если контрольная сумма равна нулю, обнаруживается ошибка. Контрольная сумма сообщения — это арифметическая сумма кодовых слов определенной длины. Сумма указывается с помощью дополнения 1 и сохраняется или передается как расширение кода фактического кодового слова. На приемнике новая контрольная сумма вычисляется путем приема битовой последовательности от передатчика.

Метод контрольной суммы включает биты четности, контрольные цифры и продольный контроль избыточности (LRC). Например, если нам нужно передать и обнаружить ошибки для длинной последовательности данных (также называемой строкой данных), мы разделим ее на более короткие слова и можем сохранить данные со словом той же ширины.Для каждого следующего входящего бита мы будем добавлять их к уже сохраненным данным. В каждом случае новое добавленное слово называется «Контрольная сумма».

На стороне приемника контрольная сумма полученных битов такая же, как и у передатчика, ошибок не обнаружено.

Мы также можем найти контрольную сумму, сложив все биты данных. Например, если у нас есть 4 байта данных как 25h, 62h, 3fh, 52h.

Затем, сложив все байты, мы получим 118H

Отбросив полубайт переноса, мы получим 18H

Найдите двойное дополнение полубайта, т.е.е. E8H

Это контрольная сумма переданных 4 бит данных.

На стороне получателя, чтобы проверить, получены ли данные без ошибок или нет, просто добавьте контрольную сумму к фактическим битам данных (мы получим 200H). Отбрасывая полубайт переноса, мы получаем 00H. Это означает, что контрольная сумма ограничена нулем. Значит, в данных нет ошибки.

В общем, существует 5 типов методов контрольной суммы, например

• Целочисленная контрольная сумма сложения
• Контрольная сумма до одного
• Контрольная сумма Флетчера
• Контрольная сумма Адлера
• Контрольная сумма ATN (AN / 466)

Пример

As Теперь мы обсудили коды обнаружения ошибок.Но для получения точной и идеальной последовательности данных без каких-либо ошибок недостаточно только обнаруживать ошибки, возникшие в данных. Но также нам необходимо скорректировать данные, исключив наличие ошибок, если они есть. Для этого мы используем некоторые другие коды.

В начало

Коды исправления ошибок

Коды, которые используются как для обнаружения ошибок, так и для исправления ошибок, называются «Кодами исправления ошибок». Методы исправления ошибок бывают двух типов. Это

• Коррекция одиночных битовых ошибок
• Пакетная коррекция ошибок

Процесс или метод исправления одиночных битовых ошибок называется «исправлением одиночных битовых ошибок».Метод обнаружения и исправления пакетных ошибок в последовательности данных называется «Коррекция пакетных ошибок».

Код Хэмминга или код расстояния Хэмминга — лучший код коррекции ошибок, который мы используем в большинстве сетей связи и цифровых системах.

В начало

Код Хэмминга

Этот метод обнаружения и исправления ошибок разработан Р. В. Хэммингом. Этот код не только идентифицирует бит ошибки во всей последовательности данных, но и исправляет его.В этом коде используется ряд битов четности, расположенных в определенных позициях кодового слова. Количество битов четности зависит от количества информационных битов. Код Хэмминга использует соотношение между битами избыточности и битами данных, и этот код может применяться к любому количеству битов данных.

Что такое бит резервирования?

Избыточность означает «разницу между количеством бит фактической последовательности данных и переданными битами». Эти биты избыточности используются в системе связи для обнаружения и исправления ошибок, если таковые имеются.

Как на самом деле код Хэмминга исправляет ошибки?

В коде Хэмминга биты избыточности помещаются в определенные расчетные позиции, чтобы исключить ошибки. Расстояние между двумя битами избыточности называется «расстоянием Хэмминга».

Чтобы понять работу и механизм исправления ошибок данных и обнаружения кода Хэмминга, давайте рассмотрим следующие этапы.

Количество битов четности

Как мы узнали ранее, количество битов четности, добавляемых к строке данных, зависит от количества информационных битов строки данных, которая должна быть передана.Количество битов четности будет вычислено с использованием битов данных. Это соотношение приводится ниже.

2 ^P > = n + P +1

Здесь n представляет количество бит в строке данных.

P представляет количество битов четности.

Например, если у нас есть 4-битная строка данных, то есть n = 4, то количество битов четности, которые нужно добавить, можно найти с помощью метода проб и ошибок. Возьмем P = 2, тогда

2 ^P = 2 ² = 4 и n + P + 1 = 4 + 2 + 1 = 7

Это нарушает фактическое выражение.

Итак, давайте попробуем P = 3, затем

2 ^P = 2 ³ = 8 и n + P + 1 = 4 + 3 + 1 = 8

Итак, мы можем сказать, что для передавать 4-битные данные с исправлением однобитовых ошибок.

Где разместить эти биты четности?

После вычисления количества требуемых битов четности мы должны знать соответствующие позиции, чтобы разместить их в информационной строке, чтобы обеспечить исправление однобитовых ошибок.

В рассмотренном выше примере у нас есть 4 бита данных и 3 бита четности.Таким образом, общее кодовое слово, которое должно быть передано, составляет 7 бит (4 + 3). Обычно мы представляем последовательность данных справа налево, как показано ниже.

бит 7, бит 6, бит 5, бит 4, бит 3, бит 2, бит 1, бит 0

Биты четности должны быть расположены в позициях степеней 2. То есть. при 1, 2, 4, 8 и 16 и т. д. Следовательно, кодовое слово после включения битов четности будет таким:

D7, D6, D5, P4, D3, P2, P1

Здесь P1, P2 и P3 — биты четности . D1 —- D7 — биты данных.

Построение таблицы расположения битов

В коде Хэмминга каждый бит четности проверяет и помогает найти ошибки во всем кодовом слове. Поэтому мы должны найти значение битов четности, чтобы присвоить им битовое значение.

Вычисляя и вставляя биты четности в биты данных, мы можем добиться исправления ошибок с помощью кода Хэмминга.

Давайте разберемся в этом наглядно на примере.

Пример:

Кодируйте данные 1101 с четностью с помощью кода Хэмминга.

Шаг 1

Вычислите необходимое количество битов четности.

Пусть P = 2, тогда

2 ^P = 2 ² = 4 и n + P + 1 = 4 + 2 + 1 = 7.

2 бита четности недостаточно для 4-битных данных.

Итак, давайте попробуем P = 3, затем

2 ^P = 2 ³ = 8 и n + P + 1 = 4 + 3 + 1 = 8

Следовательно, 3 бита четности достаточно для 4-битных данных.

Общее количество битов в кодовом слове составляет 4 + 3 = 7

Шаг 2

Создание таблицы расположения битов

Шаг 3

Определите биты четности.

Для P1: 3, 5 и 7 бит имеют три единицы, поэтому для четности P1 = 1.

Для P2: 3, 6 и 7 бит имеют две единицы, поэтому для четности P2 = 0.
Для P3: 5, 6 и 7 биты имеют две единицы, поэтому для четности P3 = 0.

Путем ввода / вставки битов четности в их соответствующие позиции можно сформировать и передать кодовое слово. Это 1100101.

ПРИМЕЧАНИЕ: Если в кодовом слове все нули (например, 0000000), то в коде Хэмминга нет ошибки.

Для представления двоичных данных в виде букв и цифр мы используем буквенно-цифровые коды.

К началу

Буквенно-цифровые коды

Буквенно-цифровые коды — это в основном двоичные коды, которые используются для представления буквенно-цифровых данных. Поскольку эти коды представляют данные символами, буквенно-цифровые коды также называются «кодами символов».

Эти коды могут представлять все типы данных, включая алфавиты, числа, знаки препинания и математические символы, в приемлемой для компьютеров форме.Эти коды реализованы в устройствах ввода-вывода, таких как клавиатуры, мониторы, принтеры и т. Д.
Раньше перфокарты использовались для представления буквенно-цифровых кодов.

Это

• код MORSE
• код BAUDOT
• код HOLLERITH
• код ASCII
• код EBCDI
• UNICODE

код MORSE

На начальном этапе эры компьютеров и цифровой электроники код Морзе очень популярен. популярный и наиболее часто используемый код. Это было изобретено Сэмюэлем Ф.Б. Морс, в 1837 году. Это был первый телеграфный код, использованный в телекоммуникациях. Он в основном используется на телеграфных каналах, радиоканалах и в органах управления воздушным движением.

Код БУДО

Этот код был изобретен французским инженером Эмилем Бодо в 1870 году. Это 5-значный код, что означает, что он использует 5 элементов для представления алфавита. Он также используется в телеграфных сетях для передачи римских чисел.

HOLLERITH Код

Этот код разработан компанией, основанной Германом Холлеритом в 1896 году.12-битный код, используемый для перфокарт в соответствии с передаваемой информацией, называется «кодом Холлерита».

КОД ASCII

ASCII означает Американский стандартный код для обмена информацией. Это самый популярный и широко используемый буквенно-цифровой код в мире. Этот код был разработан и впервые опубликован в 1967 году. Код ASCII — это 7-битный код, что означает, что этот код использует 27 = 128 символов. Сюда входят

26 строчных букв (a — z), 26 заглавных букв (A — Z), 33 специальных символа и символа (например,! @ # $ И т. Д.), 33 управляющих символа (* — + / и% и т. Д.) и 10 цифр (0-9).

В этом 7-битном коде у нас есть две части: крайние левые 3 бита и правые 4 бита. Самые левые 3 бита известны как «биты ZONE», а правые 4 бита известны как «NUMERIC биты».

8-битный код ASCII может представлять 256 (28) символов. Он называется кодами USACC-II или ASCII-8.

Пример:

Если мы хотим вывести имя LONDAN, код ASCII будет?

Эквивалент ASCII-7 L = 100 1100

Эквивалент ASCII-7 O = 100 1111

Эквивалент ASCII-7 N = 100 1110

Эквивалент ASCII-7 D = 100 0100

Эквивалент ASCII-7 A = 100 0001

Эквивалент ASCII-7 N = 100 1110

Вывод LONDAN в коде ASCII: 1 0 0 1 1 0 0 1 0 0 1 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 1 0 0 1 1 1 0.

UNICODE

Недостатки кодов ASCII и EBCDI состоят в том, что они не совместимы со всеми языками и не имеют достаточного набора символов для представления всех типов данных. Чтобы преодолеть эти недостатки, разработан UNICODE.
UNICODE — это новая концепция всех методов цифрового кодирования. Здесь у нас есть разные символы для представления каждого числа. Это наиболее продвинутый и сложный язык, способный представлять данные любого типа. ТАК это известно как «Универсальный код».Это 16-битный код, с помощью которого мы можем представить 216 = 65536 различных символов.
UNICODE разработан совместными усилиями консорциума UNICODE и ISO (Международной организации по стандартизации).

КОД EBCDI

EBCDI означает расширенный двоично-десятичный код обмена. Этот код разработан компанией IBM Inc. Это 8-битный код, поэтому мы можем представить 28 = 256 символов с помощью кода EBCDI. Сюда входят все буквы и символы, такие как 26 строчных букв (a — z), 26 заглавных букв (A — Z), 33 специальных символа и символа (например,! @ # $ И т. Д.), 33 управляющих символа (* — + / и% и т. д.) и 10 цифр (0-9).

В коде EBCDI, 8-битном коде, числа представлены двоично-десятичным кодом 8421, которому предшествует 1111.

В начало

Введение в коды исправления ошибок — Часть 2 | Программа инженерного образования (EngEd)

Исправление ошибок является одним из наиболее фундаментальных аспектов цифровой связи и отвечает за достоверность взаимодействия в реальном времени. В части 1 с помощью кода Хэмминга мы проанализировали методы исправления изолированных ошибок.В реальном мире мы не всегда можем предположить, что ошибки будут изолированными, и может произойти несколько последовательных ошибок. В этой статье мы продолжим говорить о коде Хэмминга, а также о новом коде, предназначенном для исправления этих последовательных ошибок, который называется кодом Голея.

Одно из наиболее заметных применений кода Голея было с космическими кораблями «Вояджер I» и «Вояджер II» в 1970-х годах. Передача сообщений или изображений в космосе требует способности исправлять помехи и ослабление сигнала.Код Голея может исправлять несколько последовательных ошибок, что позволяет ему хорошо работать в этих сценариях. Это не лишено недостатков. Код Голея часто требует больших вычислительных ресурсов, когда дело касается как кодирования, так и декодирования.

Код Хэмминга

С помощью кода Хэмминга $ [7,4] $, представленного в части 1, мы могли кодировать четырехбитовые входные данные в семибитовые кодовые слова. Это было сделано путем добавления трех битов четности к исходному сообщению. Эта кодировка дала нам возможность исправить одну ошибку.

$$ x_1 = m_1 \ oplus m_2 \ oplus m_4 $$

$$ x_2 = m_1 \ oplus m_3 \ oplus m_4 $$

$$ x_3 = m_2 \ oplus m_3 \ oplus m_4 $$

Биты четности можно пересчитать и использовать для исправления любой возникшей ошибки. Используя эти биты четности, мы создаем таблицу, чтобы помочь определить, какие неправильные биты четности приводят к каким ошибкам.

Коды линейного исправления ошибок

Используя код Хэмминга, мы придем к более обобщенному определению кодов с исправлением ошибок.В этом разделе мы придем к тем же математическим выводам, которые только что изложены с матрицами. Это определение предоставляет шаблон для набора кодов с исправлением ошибок, называемых линейными кодами. Это также будет полезно при построении кода Голея.

Мы хотим сузить фокус до линейных кодов, поскольку они предоставят нам эффективные методы кодирования и декодирования. Линейный код обладает тем свойством, что линейная комбинация любых двух кодовых слов также является кодовым словом. Например, 1001 001 и 1011 010 оба являются кодовыми словами кода Хэмминга, представленного выше.Поскольку код Хэмминга является линейным, линейная комбинация этих кодовых слов 0010 011 , найденная с помощью оператора XOR для каждого элемента, сама по себе является кодовым словом.

Генераторная матрица

Это свойство линейных кодов позволяет нам определять процесс кодирования любого линейного кода с помощью матрицы, называемой образующей матрицей. Чтобы закодировать сообщение, мы просто умножаем входное сообщение слева от матрицы генератора. Обратите внимание, что вместо добавления мы будем использовать оператор XOR.Вычитание также будет использовать оператор XOR, означающий, что аддитивная инверсия бита — это только он сам. Например, $ -1 = 1 $.

Для кода Хэмминга мы можем создать следующую матрицу генератора, которая математически совпадает с процедурой кодирования, представленной ранее. Напомним, что три бита четности — это $ x_1 $, $ x_2 $ и $ x_3 $, а исходные четыре бита сообщения — это $ m_1 $, $ m_2 $, $ m_3 $ и $ m_4 $.

$$ \ begin {pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\\
0 & 1 & 0 & 0 & 1 & 0 & 1 \\\
0 & 0 & 1 & 0 & 0 & 1 & 1 \\\
0 & 0 & 0 & 1 & 1 & 1 & 1 \ end {pmatrix} $

С этой образующей матрицей эта новая процедура кодирования будет следующей.

$$ \ begin {pmatrix} m_1 & m_2 & m_3 & m_4 & x_1 & x_2 & x_3 \ end {pmatrix} = \ begin {pmatrix} м_1 и м_2 и м_3 и м_4 \ end {pmatrix} \ begin {pmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 0 \\\
0 & 1 & 0 & 0 & 1 & 0 & 1 \\\
0 & 0 & 1 & 0 & 0 & 1 & 1 \\\
0 & 0 & 0 & 1 & 1 & 1 & 1 \ end {pmatrix} $

Я призываю читателя убедиться в том, что эта новая процедура кодирования математически совпадает с той, что была представлена ​​ранее.

Двоичный код Хэмминга

Используя идею создания битов четности с помощью оператора XOR, мы можем создать так называемый $ [7,4] $ — код Хэмминга. Мы объединим несколько битов, чтобы создать каждый бит четности для этого кода. Этот код примет четырехбитный ввод и закодирует его в семибитное кодовое слово. Этот процесс добавит три дополнительных бита четности. Для простоты назовем три бита четности $ x_1 $, $ x_2 $ и $ x_3 $ и четыре исходных бита сообщения $ m_1 $, $ m_2 $, $ m_3 $ и $ m_4 $.

Наша цель — использовать эти биты четности для декодирования. Для этого мы можем позволить каждому из них содержать данные трех из четырех исходных битов. Это позволит нам использовать неправильные биты четности, чтобы определить, где произошла ошибка.

Мы можем определить первый бит четности как $ x_1 = m_1 \ oplus m_2 \ oplus m_4 $. При попытке декодирования, если мы определяем, что этот бит четности неверен, мы знаем, что ошибка должна была произойти с одним из четырех битов в уравнении: $ m_1 $, $ m_2 $, $ m_4 $ или $ x_1 $.

Если мы создадим два других бита четности аналогичным образом, мы получим следующие определения. С этим определением этот код будет иметь расстояние Хэмминга, равное трем.

$$ x_1 = m_1 \ oplus m_2 \ oplus m_4 $$

$$ x_2 = m_1 \ oplus m_3 \ oplus m_4 $$

$$ x_3 = m_2 \ oplus m_3 \ oplus m_4 $$

С помощью этих битов четности мы можем определить, где произошла ошибка в семибитном сообщении, зная, какие биты четности неверны. Важно отметить, что мы должны предполагать, что произошла не более одной ошибки.Исправить более одной ошибки будет невозможно, и наш код исправит другой бит. Мы могли представить себе создание графа, аналогичного тому, что мы делали раньше. Мы бы увидели, что две ошибки затем подтолкнули бы наше сообщение к другому допустимому кодовому слову, что мы и видим с кодом повторения.

Матрица проверки на четность

Нам также нужен способ обнаружения ошибок с этим новым определением. Для этой цели будет создана вторая матрица, называемая матрицей проверки на четность.С помощью матрицы проверки на четность мы вычислим то, что называется синдромом, умножив полученное сообщение слева от транспонированной матрицы проверки на четность.

Синдром, как можно предположить из определения этого слова, связан с конкретной произошедшей ошибкой и не имеет отношения к сообщению. В общем, синдром будет нулевым вектором, когда ошибка не возникает, и ненулевым вектором, когда она есть. Для кода Хэмминга синдром точно скажет нам, какие биты четности были неправильными.Матрица проверки на четность для кода Хэмминга будет следующей.

$$ \ begin {pmatrix} 1 & 1 & 0 & 1 & 1 & 0 & 0 \\\
1 & 0 & 1 & 1 & 0 & 1 & 0 \\\
0 & 1 & 1 & 1 & 1 & 0 & 0 & 1 \ end {pmatrix} $

А синдром можно найти, умножив закодированное сообщение на транспонирование матрицы проверки на четность.

$$ \ begin {pmatrix} S_1, S_2 и S_3 \ end {pmatrix} = \ begin {pmatrix} m_1 & m_2 & m_3 & m_4 & x_1 & x_2 & x_3 \ end {pmatrix} \ begin {pmatrix} 1 & 1 & 0 & 1 & 1 & 0 & 0 \\\
1 & 0 & 1 & 1 & 0 & 1 & 0 \\\
0 & 1 & 1 & 1 & 1 & 0 & 0 & 1 \ end {pmatrix} ^ T $

Присмотревшись к матрице проверки на четность, мы видим, что каждый столбец соответствует одному из случаев декодирования кода Хэмминга.T $ соответствует некорректным битам четности $ x_1 $ и $ x_2 $, т.е. в $ m_1 $ произошла ошибка. Каждый столбец соответствует тому, какие биты четности будут неправильными для того, чтобы этот столбец закодированного сообщения содержал ошибку. Следовательно, вычисление синдрома для этого кода Хэмминга дает нам столбец матрицы проверки на четность, который относится к ошибке в сообщении. Например, предположим, что у нас есть сообщение 0000 000 , но любое сообщение будет иметь тот же результат. Теперь рассмотрим ошибку в четвертом бите.Когда мы вычисляем синдром, мы получим $ \ begin {pmatrix} 1 & 1 & 1 \ end {pmatrix} $, которое мы можем более просто записать как 111 . Обратите внимание, что это четвертый столбец матрицы проверки на четность, поэтому мы знаем, что ошибка была в четвертом столбце сообщения.

Для кода Хэмминга мы можем декодировать сообщение, просто вычислив синдром и затем найдя соответствующий столбец матрицы проверки на четность. Наконец, мы можем исправить этот столбец в сообщении. Я снова призываю читателя убедиться, что этот метод математически совпадает с тем, что было представлено в предыдущем разделе.

Реализацию, использующую это новое определение, можно найти здесь.

Этот процесс декодирования уникален для кода Хэмминга, но подчеркивает полезность синдрома. Для кодов, которые могут исправить более одной ошибки, этот метод уже не так прост. Мы все еще можем использовать синдром аналогичным образом, с его расшифровкой.

Расшифровка синдрома

Декодирование синдромов работает путем построения таблицы, сопоставления синдромов с соответствующими ошибками. Мы достигаем этого, вычисляя синдром всех возможных исправимых ошибок.С помощью этой таблицы мы можем автоматически определить, содержит ли полученное сообщение ошибку и что это за ошибка, все, что нам нужно сделать, это вычислить ее синдром. Это не всегда идеальное решение для декодирования, поскольку чем больше становится код, тем больше возможных ошибок, а это означает, что размер нашей таблицы синдромов начнет экспоненциально расти. Хотя это все еще эффективное решение для кодов Хэмминга и Голея.

Давайте рассмотрим пример декодирования синдрома с помощью кода Хэмминга.Для начала нам нужно рассчитать и составить таблицу всех возможных синдромов. Это должно выглядеть очень похоже на таблицу, которую мы создали в предыдущем разделе.

Теперь рассмотрим пример, в котором мы хотим передать сообщение 1011 .Сначала мы кодируем его в сообщение 1011010 . Теперь во время передачи третий бит испытывает ошибку и переворачивается, что приводит к получению сообщения 1001010 . Расчет синдрома этого сообщения даст нам синдром 011 . Используя таблицу, мы можем сопоставить этот синдром с ошибкой 0010 000 . Наконец, мы можем поменять местами этот бит, что приведет к исходному закодированному сообщению.

Стандартная форма

Мы говорим, что код имеет стандартную форму, если его порождающая матрица выражается как расширенная матрица $ G = \ left (I_k | X \ right) $.Т | I_ {n-k} \ right) $. Для этого определения переменная $ k $ представляет размер входящего сообщения, а $ n $ представляет размер закодированного сообщения.

Обратите внимание, что в стандартной форме обе матрицы имеют общую подматрицу $ X $. Это означает, что легко построить одну из матриц, если мы уже знаем другую. Эту общую матрицу можно увидеть с помощью кода Хэмминга, поскольку и генераторная, и контрольная матрицы используют матрицу, показанную ниже. Обратите внимание, что каждый из столбцов этой матрицы представляет один из битов четности для кода Хэмминга.

$$ X = \ begin {pmatrix} 1 & 1 & 0 \\\
1 & 0 & 1 \\\
0 & 1 & 1 \\\
1 & 1 & 1 \ end {pmatrix} $

И генератор, и матрица проверки на четность будут содержать единичную матрицу, что означает, что первые несколько битов всегда будут исходным сообщением.

Двоичный код Голея

Код Голея принимает 12-битный вход и кодирует его в 23-битное кодовое слово. Этот процесс кодирования добавляет 11 битов четности, что дает этому коду расстояние Хэмминга, равное семи, что означает, что мы можем исправить до трех ошибок.Как упоминалось в предыдущем разделе, чтобы определить линейный код в стандартной форме, достаточно знать только общую подматрицу. Для кода Голея мы определим эту подматрицу как матрицу $ A $, показанную ниже.

$$ A = \ begin {pmatrix} 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\\
1 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\\
1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \\\
1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\\
1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \\\
1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\\
1 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 \\\
1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\\
1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 \\\
1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 \\\
1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 \\\
1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \ end {pmatrix} $

Это довольно устрашающая матрица, поэтому давайте разберемся, что она означает.По своей сути эта матрица очень похожа на подматрицу кода Хэмминга. Он сообщает нам, как определяются биты четности. Например, первые строки говорят нам, что первый бит четности — это комбинация, использующая XOR, всех битов в исходном сообщении, кроме первого.

Зная, что код Голея линейен, у нас уже есть метод кодирования и декодирования наших сообщений. Давайте посмотрим, как этот процесс применим к коду Голея. Для простоты мы будем называть 12-битное входное сообщение $ \ vec {m} $, а 23-битное полученное сообщение $, \ vec {w} $.Т | I_ {11} \ right) $. Чтобы кодировать, мы можем умножить наше входное сообщение слева от нашей матрицы генератора.

Зная, что первые 12 бит будут исходным сообщением, мы можем уменьшить количество необходимых вычислений, поскольку нам нужно только вычислить биты четности. Это можно сделать, умножив исходное сообщение слева от матрицы $ A $. Закодированное сообщение представляет собой конкатенацию исходного сообщения и битов четности.

$$ (\ vec {m} | \ vec {x}) = (\ vec {m} | \ vec {m} \ cdot A) $$

Чтобы найти синдром, мы будем использовать то же определение, что и в предыдущем разделе: умножение полученного сообщения $ w $ на транспонирование матрицы проверки на четность.Т $

Теперь, когда у нас есть способ вычислить синдром, мы можем применить декодирование синдрома, как упомянуто в предыдущем разделе. Реализацию синдромного декодирования кода Голея с генератором случайных ошибок можно найти здесь.

Заключение

Теперь, когда мы проанализировали код Голея, давайте поговорим о статистике того, насколько хорошо мы ожидаем, что он будет работать. Например, предположим, что мы передаем трехмегабайтное изображение по каналу связи с вероятностью ошибки 0.01. Мы ожидаем, что в закодированном изображении будет 460 000 ошибочных битов. Когда мы получим это изображение и начнем декодирование, мы сможем исправить 99,99% всех полученных 23-битных сегментов. Таким образом, с помощью кода Голея мы ожидаем, что сможем исправить подавляющее большинство ошибок. После исправления ошибок мы ожидаем менее 50 ошибочных битов.

Дополнительная литература

Если вам интересно узнать больше о кодах с исправлением ошибок, особенно с акцентом на математику, я бы посоветовал прочитать здесь конспекты лекций.