Двухуровневое устройство исправления ошибок

 

Использование: изобретение относится к вычислительной технике и предназначено для использования в многоканальных устройствах регистрации цифровой информации для исправления одноканальных ошибок любой длины и пакетов ошибок длиной m - 1. Сущность изобретения: с целью повышения достоверности считанной информации за счет исправления пакетов ошибок при увеличении плотности информации устройство содержит два уровня исправления ошибок, каждый из которых содержит блок регистров, блок свертки по модулю два наклонной четности, два элемента НЕРАВНОЗНАЧНОСТЬ, блоки обнаружения ошибки по числу разрядов в каждом уровне, блок определения многократной ошибки, регистр сдвига, группу элементов И, блок сумматоров по модулю два, элемент НЕ, выходную шину. Второй уровень исправления ошибок содержит регистр ступенчатого сдвига информации с нарастанием сдвига с n-го разряда до первого со ступенью m. Устройство позволяет исправлять одиночные ошибки на первом уровне, используя вторую вертикальную и наклонную четности, при этом первая вертикальная и наклонная четности принимаются как N + 1 и N + 2 информационные разряды и пакеты ошибок длиной m - 1, которые на втором уровне преобразуются регистром ступенчатого сдвига, одиночные ступенчато-сдвинутые ошибки, исправление которых осуществляется парной наклонной и вертикальной четностями, что повышает достоверность считанной информации. 6 ил.

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

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

Наиболее близким к заявляемому является многоканальное устройство исправления ошибок для магнитных накопителей [2] которое содержит блок регистров сдвига, блок свертки по модулю два вертикальной четности, блок свертки по модулю два наклонной четности, первый и второй элементы неравнозначности, группу триггеров, четыре группы элементов И, блок обнаружения многократной ошибки, регистр сдвига, группу элементов НЕ, элемент НЕ, сумматоры по модулю два. Данное устройство позволяет исправлять ошибки, одновременно возникающие только в одном канале.

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

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

Цель изобретения повышение достоверности считанной информации при увеличении поперечной плотности записи за счет исправления пакетов ошибок. Отличие от известного заключается в том, что двухуровневое устройство исправления ошибок для магнитных накопителей, содержащее в каждом уровне регистр сдвига, блок свертки по модулю два вертикальной четности, блок свертки по модулю два наклонной четности, два элемента "Неравнозначность", блок многократной ошибки, группу из N элементов И по числу разрядов информации, N сумматоров по модулю два, N последовательно соединенных блоков обнаружения ошибки и блок регистров сдвига, выходы которого в каждом уровне подключены к блоку свертки по модулю два вертикальной четности и к первым входам сумматоров, вторые входы которых соединены с выходами элементов группы, а выходы сумматоров второго уровня являются выходами устройства, выход регистра сдвига в каждом уровне соединен с одним входом первого элемента "Неравнозначность", другой вход которого соединен с выходом блока свертки вертикальной четности, выход которого соединен с вторыми входами каждого из N блоков обнаружения ошибки, первые выходы которых подключены к первым входам соответствующего элемента И группы, и установочным входам блока многократной ошибки, а второй выход каждого последующего блока соединен с вторым входом предыдущего блока определения ошибки, выход блока многократной ошибки соединен с выходной шиной устройства в каждом уровне и через элемент НЕ с вторыми входами каждого из элементов И группы, выход блока свертки по модулю два наклонной четности через второй элемент "Неравнозначность" соединен с входом первого блока обнаружения ошибки, а информационные входы блока регистров сдвига и блока свертки по модулю два наклонной четности первого уровня поразрядно соединены и являются информационными входами устройства, тактовые входы регистров сдвига и входы синхронизации блоков определения ошибки первого и второго уровней объединены и соединены с входом синхронизации устройства, введены в первый уровень информационная шина второй вертикальной четности, подключенная к регистру сдвига, шина второй наклонной четности, подключенная к входу второго элемента "Неравнозначность", два блока N+1, N+2 обнаружения ошибки, два элемента И N+1 и N+2, два сумматора N+1 и N+2, и выполнен на N+2 разряда информации, второй уровень содержит регистр ступенчатого сдвига на N+1 разряд, входы которого соединены с выходами первого уровня устройства, а выходы N разрядов подключены к соответствующим входам регистра сдвига, выход первой наклонной четности соединен с вторым входом второго элемента "Неравнозначность".

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

На фиг. 1, 2 представлена структурная схема устройства; на фиг.3 блок обнаружения многократной ошибки первого уровня; на фиг.4 блок обнаружения многократной ошибки второго уровня; на фиг.5,6 схема, поясняющая работу устройства по исправлению ошибок.

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

Каждый уровень содержит блок регистров сдвига, в первом уровне 1₁¹. 1_N+2¹, во втором уровне 1₁².1_N², блок 2 свертки по модулю два вертикальной четности, блок 3 свеpтки по модулю два наклонной четности, два элемента "Неравнозначность" 4,5, блок 6 обнаружения ошибки по числу разрядов в каждом уровне (в первом на N+2 разряда, во втором на N разрядов), блок 7 обнаружения многократной ошибки, регистр 8 сдвига, группу элементов И 9, блок 10 сумматоров по модулю два, элемент НЕ 11 и выход 12 многократной ошибки.

Кроме того, второй уровень исправления ошибки содержит регистр 13 ступенчатого сдвига, информации с нарастанием сдвига с N-го разряда до первого со ступенью m (m=2,3,4,).

Информационные входы блока 1₁¹.1_N+2¹ pегистров сдвига и блока свертки наклонной четности первого уровня 3¹ поразрядно объединены и соединены с информационными входами устройства, выходы блока 1 регистров в каждом уровне подключены к входам блока 2 свертки вертикальной четности и первым входам блока 10 сумматоров по модулю два, вторые входы которых подключены к выходам элементов И9 группы.

Выход блока 2 свертки по модулю два вертикальной четности подключен к первому входу первого элемента "Неравнозначность" 4, второй вход которого подключен к выходу регистра 8 сдвига, а выход подключен к входам последовательно соединенных блоков 6 обнаружения ошибок, количество которых в каждой ступени определяется числом разрядов информации. Выход блока 3 свертки по модулю два наклонной четности соединен с вторым входом второго элемента "Неравнозначность" 5, выходом соединенного с информационным входом первого блока 6 обнаружения ошибки.

Первые выходы блоков 6 обнаружения ошибки в каждом уровне подключены к установочным входам блока 7 многократной ошибки и первым входам элементов И9 группы, а вторые выходы каждого последующего блока 6 соединены с вторыми входами предыдущего.

Вторые входы элемента И9 группы соединены и через элемент НЕ11 подключены к выходу блока 7 многократной ошибки и выходной шине 12 многократной ошибки.

Входы второй вертикальной и наклонной четностей первого уровня соединены соответственно с входом регистра 8¹ сдвига и входом второго элемента "Неравнозначность" 5¹.

Выходы первого уровня исправления ошибок соединены с соответствующими информационными входами блока 13 регистров ступенчатого сдвига второго уровня. Выход блока 13 регистров поразрядно соединены с входами блока регистров 1₁².1_N² и входами блока 3² свертки по модулю два наклонной четности, а выход подключен к второму входу второго элемента "Неравнозначность" 5².

Вход синхронизации устройства соединен с тактовыми входами регистров и входами синхронизации блоков обнаружения ошибок.

Каждый блок 6 обнаружения ошибки содержит триггер 14, первый, второй, третий элементы И15, 16, 18, элемент НЕ 17.

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

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

На фиг.3 представлен блок 7¹ определения многократной ошибки первого уровня исправления, который содержит группу элементов И19¹, количество которых определяется как N/2+1, группу триггеров 20¹, количество которых равно N+2, объединенных в пары, число которых равно N/2+1, каждая пара подключена к выходу соответствующего элемента И19¹ группы, мажоритарный элемент 21¹.

Блок 7² определения многократной ошибки второго уровня исправления (фиг. 4) аналогичен по схемному решению блоку 7¹, но выполнен на N разрядов информации и содержит группу из N/2 элементов И19² и группу из N триггеров 20², объединенных в N/2 пар, мажоритарный элемент 21².

Устройство работает следующим образом.

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

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

N разрядов цифровой информации (фиг. 1), сигнал первой вертикальной четности и сигнал первой наклонной четности сопровождаются единой синхронизацией. СИ поступает на первый уровень исправления, на блок 3¹ свертки по модулю два, на выходе которого формируется сигнал второй наклонной четности, и через блок 1¹ регистров, обеспечивающих ступенчатый сдвиг, поступает на блок 2¹ свертки по модулю два, на выходе которого формируется сигнал второй вертикальной четности. Сформированный сигнал второй наклонной четности с блока 3¹ и сигнал второй наклонной четности, считанной с магнитного носителя, подаются на элемент "Неравнозначность" 5¹, на выходе которого вырабатывается сигнал несоответствия вторых наклонных четностей. Сформированный сигнал второй вертикальной четности с блок 2¹ подается на один из входов элемента "Неравнозначность" 4¹, на другой вход которого подается сигнал считанной второй вертикальной четности через регистр 8¹, обеспечивающий сдвиг данного сигнала на N+2 такта.

При несовпадении сигналов сформированной и считанной четностей (вертикальной или наклонной) на выходе элементов "Неравнозначность" формируется сигнал несоответствия четностей (признак ошибки).

Сигнал несоответствия вторых наклонных четностей в случае отсутствия сигнала несоответствия вертикальных четностей переписывается с одного блока 6¹ в последующий (в триггеры 14₁.14_N+2 через элементы И16₁.16_N+2) синхронно с передачей информации в регистры 1¹, 8¹. В случае появления сигнала несоответствия вторых вертикальных четностей признака ошибки на входах блоков 6¹ и при наличии сигнала несоответствия вторых наклонных четностей, записанных в блоки 6¹, триггеры 14, а также при отсутствии сигналов запрета с последующего блока 6¹ определения ошибки, с элемента И18, с выхода блока 6¹ элемент И15¹ снимает сигнал коррекции информации. Он подается на один из входов соответствующего элемента И9¹ и на вход установки в "1" соответствующего триггера 19¹ блока 7¹ обнаружения ошибки. Сигнал коррекции (с элемента И15¹ через элемент НЕ17 и элемент И16¹) запрещает прохождение сигнала несоответствия вторых наклонных четностей на последующий блок 6¹ (триггер 14¹) и через элемент И18¹ запрещает выделение сигнала коррекции на предыдущем блоке 6 элемента И15¹. При искажении информации, например в i-м разряде, сигналы несоответствия вторых вертикальных и наклонных четностей совпадают на входах i-го элемента И15¹, на выходе которого выделяется сигнал коррекции информации. Сигнал коррекции информации через элемент НЕ17¹ запрещает прохождение сигнала несоответствия вторых наклонных четностей на вход (i+1)-го блока 6¹, триггер 14¹ и через элемент НЕ17¹ и элемент И18¹ запрещает выделение сигнала коррекции (i-1)-х блоков элементом И15¹. Сигнал коррекции информации с выхода i-го блока 6 элемента И15 подается на i-й элемент И9¹ и на вход установки в "1" i-го триггера 20 блока 7¹, устанавливая его в единичное состояние. Сигнал с выхода i-го триггера 20¹ поступает на мажоритарный элемент 21¹, который формирует единичный сигнал при наличии двух или более единиц на его входах, поэтому при искажении информации только в i-м разряде (единичная ошибка) с выхода мажоритарного элемента 21¹ снимается нулевой потенциал. При установке в единичное состояние триггеров 20, количество которых совпадает с функцией мажоритарного элемента 21¹, т.е. больше или равно двум, им вырабатывается сигнал "Многократная ошибка", который подается на выходную шину 12¹ и через элемент НЕ11¹ на один из входов элементов И9¹, запрещая прохождение сигналов коррекции информации на входы сумматоров 10. Информация, поступающая на другие входы сумматоров 10¹ с буферных регистров 1¹, без изменения передается на выход. Сигнал с выхода мажоритарного элемента 21¹ блока 7¹ несет сообщение о наличии во входной информации двойной ошибки или ошибки большей кратности.

Запрет на коррекцию информации снимается обнулением триггеров 20₁¹. 20_N+2¹, которое осуществляется дифференциально для каждой пары разрядов информации в зависимости от его позиции. Конец запрета на коррекцию первой пары разрядов (N/2+1) и (N/2+2) информации определяется обнулением триггеров 20¹ N/2+1 и 20¹N/2+2, которое происходит через элемент И19¹ при наличии единиц на инверсных выходах триггеров 14¹ N/2+1 и 14¹N/2+2. В такое состояние они устанавливаются при отсутствии искажений в N/2+1 и N/2+2 разрядах информации. Конец запрета на коррекцию N/2 и N/2+3 разрядов информации определяется обнулением триггеров 20¹N/2 и 20¹N/2+3, которое происходит через элемент И19² при наличии единиц на инверсных выходах триггеров 14¹N/2, 14¹N/2+1, 14¹N/2+2, 14¹N/2+3, в такое состояние они устанавливаются при отсутствии искажений в N/2, N/2+1, N/2+2, N/2+3 разрядах информации.

Конец запрета на коррекцию сигнала первой наклонной четности и сигнала первой вертикальной четности определяется обнулением триггеров 20₁¹ и 20¹_N+2, которое происходит через элемент И19¹_N/2+1 при наличии единиц на инверсных выходах триггеров 14₁¹.14_N+2¹. В такое состояние они устанавливаются при отсутствии искажений во всех N разрядах информации и сигналах первой наклонной и первой вертикальной четностей. В N разрядах цифровой информации и сигналах первых вертикальной и наклонной четностей на выходе сумматора 10¹ по модулю два исправлены все одноканальные ошибки, но не исправлены пакеты ошибок. Для исправления пакетов ошибок длиной m-1 с выхода сумматора 10¹ по модулю два N разрядов цифровой информации и сигналы первых вертикальной и наклонной четностей подаются на второй уровень исправления (фиг.2). Блок 13 регистров ступенчатого сдвига проводит ступенчатый сдвиг информации с нарастанием с N-го по первый разряд с шагом ступени, равным m. В результате такого сдвига информации пакеты ошибок длиной m-1 преобразуют в одноканальные ошибки (фиг.5, 6), где на фиг.5 представлен пакет ошибок, возникший в процессе считывания и не исправленный в первом уровне, на фиг.6 представлен этот же пакет ошибок после сдвига в регистрах блока 13, преобразованный в одноканальные ошибки, сдвинутые во времени.

С выхода блока 13 регистров ступенчатого сдвига N разрядов цифровой информации поступают на блок 3² свертки по модулю два, на выходе которого формируется сигнал первой наклонной четности, и через блок 1² регистров, обеспечивающих ступенчатый сдвиг, поступает на блок 2² свертки по модулю два, на выходе которого формируется сигнал первой вертикальной четности. Далее работа второй ступени аналогична первой. Сформированный сигнал первой наклонной четности с блока 3² и сигнал первой наклонной четности, поступающий с блока 13² ступенчатого сдвига, подаются на элемент "Неравнозначность" 5², на выходе которого вырабатывается сигнал несоответствия первых наклонных четностей. Сформированный сигнал первой вертикальной четности с блока 2² подается на один из выходов элемента "Неравнозначность" 4², на другой вход которого подается сигнал первой вертикальной четности, поступающий с блока 10¹ сумматоров по модулю два первого уровня через регистр 8². На выходе элемента "Неравнозначность" 4² формируется сигнал несоответствия первых вертикальных четностей. Сигнал несоответствия первых наклонных четностей в случае отсутствия сигнала несоответствия первых вертикальных четностей переписывается с одного блока 6² в следующий синхронно с передачей информации в регистры 1² и 8². В случае появления сигнала несоответствия первых вертикальных четностей, наличия сигнала несоответствия первых наклонных четностей, записанных в блоки 6², и отсутствия сигналов запрета с последующих блоков 6² на выходе их вырабатывается сигнал коррекции. Он подается на один из входов соответствующего элемента И9² и на вход установки в "1" соответствующего триггера блока 7² обнаружения многократной ошибки. Сигнал коррекции с элемента И15² через элемент НЕ17² запрещает прохождение сигнала несоответствия первых наклонных четностей через элемент И16². На последующий блок 6² триггер 14² и через элемент И18² запрещает выделение сигнала коррекции на предыдущий блок 6² элемент И15². При искажении информации, например в К-м разряде, сигналы несоответствия первых вертикальных и наклонных четностей совпадают на входах К-го элемента И15², на выходе которого выделяется сигнал коррекции информации. Сигнал коррекции, информации через элемент НЕ17² запрещает прохождение сигнала несоответствия первых наклонных четностей на вход (К+1)-го триггера 14² и через элемент НЕ17² и элемент И18² запрещает выделение сигнала коррекции (К-1)-м элементом И15². Сигнал коррекции информации с выхода К-го блока 6², элемента 5² подается на К-й элемент И9² и вход установки в "1" К-го триггера 20², блока 7², устанавливая его в единичное состояние. Сигналы с выхода К-го триггера 20² поступают на мажоритарный элемент 21², который формирует единичный сигнал при наличии двух или более единиц на его входах, поэтому при искажении информации только в К-м разряде с выхода мажоритарного элемента 21² снимается нулевой потенциал. При установке в единичное состояние триггеров 20², количество которых совпадает с функцией мажоритарного элемента 21², т.е. больше или равно двум, им вырабатывается сигнал и многократная ошибка 2, которые подаются на выходную шину 12² и через элемент НЕ11² на один из входов элементов И9², запрещая прохождение сигналов коррекции информации на входы сумматоров 10² с буферных регистров 1², которые без изменения передаются на выход устройства. Сигнал с выхода мажоритарного элемента 21² блока 7² несет сообщение о наличии во входной информации двойной ошибки или ошибки большей кратности. Конец запрета на коррекцию N/2 и N/2+1 разрядов информации определяется обнулением триггеров 20²N/2 и 20²N/2+1, которое происходит через элемент И19₁² при наличии единиц на инверсных выходах триггеров 14²N/2 и 14N/2+1. В такое состояние они устанавливаются при отсутствии искажений в N/2 и N/2+1 разрядах информации. Конец запрета на коррекцию N/2-1 и N/2+2 разрядов информации определяется обнулением триггеров 20² N/2-1 и 20² N/2+2, которое происходит через элемент И 14² при наличии единиц на инверсных выходах триггеров 14² N/2-1, 14² N/2, 14² N/2+1, 14² N/2+2. В такое состояние они устанавливаются при отсутствии искажений в N/2-1, N/2, N/2+1, N/2+2 разряда информации и т.д.

Конец запрета на коррекцию первого и N-го разрядов информации определяется обнулением триггеров 20₁² и 20_N², которое происходит через элемент И19 N/2 при наличии единиц на инверсных выходах триггеров 14₁.14_N. В такое состояние они устанавливаются при отсутствии искажений во всех N разрядах.

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

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

Формула изобретения

ДВУХУРОВНЕВОЕ УСТРОЙСТВО ИСПРАВЛЕНИЯ ОШИБОК, содержащее в каждом уровне регистр сдвига, блок свертки по модулю два вертикальной четности, блок свертки по модулю два наклонной четности, два элемента НЕРАВНОЗНАЧНОСТЬ, блок многократной ошибки группы из N элементов И по числу разрядов информации, N сумматоров по модулю два, элемент НЕ, N последовательно соединенных блоков обнаружения ошибки и блок регистров сдвига, выходы которого в каждом уровне подключены к блоку свертки по модулю два вертикальной четности и к первым входам сумматоров, вторые входы которых соединены с выходами элементов И группы, а выходы сумматоров второго уровня являются выходами устройства, выход регистра сдвига в каждом уровне соединен с одним входом первого элемента НЕРАВНОЗНАЧНОСТЬ, другой вход которого соединен с выходом блока свертки вертикальной четности, выход которого соединен с вторыми входами каждого из N блоков обнаружения ошибки, первые выходы которых подключены к первым входам соответствующего элемента И группы, и установочным входам блока многократной ошибки, а второй выход каждого последующего блока соединены с третьим входом предыдущего блока определения ошибки, выход блока многократной ошибки соединен с выходной шиной устройства первого и второго уровня и через элемент НЕ с вторыми входами каждого из элементов И группы, выход блока свертки по модулю два наклонной четности через второй элемент НЕРАВНОЗНАЧНОСТЬ соединен с первым входом первого блока обнаружение ошибки, а информационные входы блока регистров сдвига и блока свертки по модулю два наклонной четности первого уровня поразрядно соединены и являются информационными входами устройства, тактовые входы регистров сдвига и входы синхронизации блоков обнаружения ошибки первого и второго уровня объединены и соединены с входом синхронизации устройства, отличающееся тем, что первый уровень устройства содержит информационную шину второй вертикальной четности, подключенную к регистру сдвига, шину второй наклонной четности, подключенную к входу второго элемента НЕРАВНОЗНАЧНОСТЬ, два блока N + 1, N + 2 обнаружения ошибки, два N + 1 и N + 2 элемента И, два N + 1 и N + 2 сумматора и выполнены на N + 2 разряда информации, второй уровень содержит регистр ступенчатого сдвига на N + 1 разряд, входы которого соединены с выходами первого уровня устройства, а выходы N разрядов подключены к соответствующим входам регистра сдвига, информационный выход первой наклонной четности соединен с вторым входом второго элемента НЕРАВНОЗНАЧНОСТЬ.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6