Как Код Хемминга работает?
Ledger API позволяет выполнять потоковую передачу транзакций, созданных в регистре, с использованием gRPC. Используя любой клиент, сгенерированный gRPC, вы можете реализовать фильтр, преобразование или агрегирование транзакций в вашем коде. Определение protobuf конечной точки службы для подключения таково:
service TransactionService {
// Read the ledger's filtered transaction stream for a set of parties.
rpc GetTransactions (GetTransactionsRequest) returns (stream GetTransactionsResponse);
}
В Java, например, подписка на поток транзакций будет выглядеть следующим образом:
public class Main {
private static void processTransaction(TransactionOuterClass.Transaction tx) {
// process (filter, transform, aggregate) transaction
System.out.printf("received transaction %s\n", tx.getTransactionId());
}
public static void main(String[] args) {
// Create a GRPC channel
ManagedChannel channel = ManagedChannelBuilder.forAddress("localhost", 7600).usePlaintext().build();
// Get ledger identity
LedgerIdentityServiceBlockingStub ledgerIdService = LedgerIdentityServiceGrpc.newBlockingStub(channel);
GetLedgerIdentityResponse identityResponse = ledgerIdService.getLedgerIdentity(GetLedgerIdentityRequest.getDefaultInstance());
String ledgerId = identityResponse.getLedgerId();
// Subscribe observer to transaction stream
String party = "Alice";
TransactionServiceStub transactionService = TransactionServiceGrpc.newStub(channel);
GetTransactionsRequest transactionsRequest = GetTransactionsRequest.newBuilder()
.setLedgerId(ledgerId)
.setBegin(LedgerOffset.newBuilder().setBoundary(LedgerOffset.LedgerBoundary.LEDGER_BEGIN))
.setFilter(TransactionFilter.newBuilder().putFiltersByParty(party, Filters.getDefaultInstance()))
.build();
StreamObserver<GetTransactionsResponse> transactionObserver = new StreamObserver<GetTransactionsResponse>() {
@Override
public void onNext(GetTransactionsResponse value) {
value.getTransactionsList().forEach(Main::processTransaction);
}
@Override
public void onError(Throwable t) {
System.err.printf("%s encountered an error while processing transactions!\n", party);
t.printStackTrace();
}
@Override
public void onCompleted() {
System.out.printf("%s's transactions stream completed.\n", party);
}
};
System.out.printf("%s starts reading transactions.\n", party);
transactionService.getTransactions(transactionsRequest, transactionObserver);
try {
Thread.sleep(Long.MAX_VALUE);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
Обратите внимание, что это используя необработанный код, сгенерированный GRPC. В SDK также доступны реактивные привязки, которые делают вышеупомянутое менее многословным.
6 ответов
Давайте попытаемся объяснить это немного:
У нас есть число на 3 бита. Возможности могут быть представлены как куб, где каждый бит представляет ось. Эти восемь возможностей находятся на углах.
000 --------001
| \ | \
| 100---------101
| | | |
| | | |
010-|-------011 |
\| \|
110---------111
Каждый дефект (например, 101 читается как 100), результаты в сдвиге на строке на кубе.
Если мы используем два бита для данных, и третье для проверки четности (скажите, например, даже что четность). Мы теряем 4 точки данных. Но это имеет преимущество, что мы можем обнаружить единственный разрядный отказ (который преобразовывает даже количество 1's в нечетное количество). Нечетные числа отмечены с *. И мы видим, что каждый нечетный (неправильно переданный) слово загнан в угол даже (законно переданный) слова. Таким образом, если мы получаем 100, мы можем быть уверены, что это неправильно.
Но (с единственным разрядным отказом) корректное представление, возможно, было 000, 101 или 110. Таким образом, мы можем обнаружить что-то, было неправильным, но мы не можем обнаружить то, что было неправильным:
000 -------*001
| \ | \
|*100---------101
| | | |
| | | |
*010-|-------011 |
\| \|
110--------*111
Это называют одним кодом обнаружения битовой ошибки.
Если мы используем другой бит для проверки и таким образом удаляем один для данных. Нас оставляют с 1 битом данных и 2 "контрольными битами". В этом случае, позволяет, принимают 000, и 111 допустимые представления данных, и другие шесть не. Теперь у нас есть интересная ситуация, если один бит искажается во время транспорта. Если мы отправляем 000 и получаем 010, мы видим, что 010 имеет одного допустимого соседа (000) и два недопустимых (110 и 011). Таким образом, теперь мы знаем, что намеревались отправить 000 и можем исправить это:
000 -------*001
| \ | \
|*100--------*101
| | | |
| | | |
*010-|------*011 |
\| \|
*110---------111
Это называют одним кодом исправления битовой ошибки.
Обратите внимание на то, что один код исправления битовой ошибки является также двухбитовым кодом с обнаружением ошибок.
И помещать его в более общем плане.
Если у Вас есть n контрольные биты, у Вас есть n код обнаружения битовой ошибки. Если Вы имеете 2n контрольные биты, у Вас есть n код исправления битовой ошибки.
Конечно, необходимо заказать "действительные" коды так, чтобы они не граничили друг с другом.
Вот действительно общий обзор.
Suppose that every time I send a message, I send thrie copies of the text.
Suppose that every time I send z message, I send three copies of the teyt.
Suppose that every tyme I send a message, I send three copies if the tezt.
Путем сравнения символов и взятия голосования простым большинством в каждом положении, можно исправить единственные ошибочные символы. Однако стоимость этой схемы (объем данных, который должен быть отправлен) высока, и это не ловит маловероятный-но-возможный случай двух ошибок в соответствующих положениях различных копий (как в последнем слове образца выше).
Коды Хемминга (и другие виды кодов с коррекцией ошибок, такие как Тростник-Solomon) основаны на формулах, которые вычисляют дополнительные данные (а не простое дублирование). Добавленные биты зависят от комбинаций битов данных способом, что ошибки в копировании делают обнаруживаемые шаблоны изменений, когда вычисление повторяется в принимающем конце.
Ради иллюстрации давайте запустимся с простой отрицательной четности, добавив единственный бит, чтобы гарантировать, что общее количество битов в сообщении нечетно. Так сообщение 10110110 становится 101101100 (пять 1 с, никакой дополнительный необходимый 1) и сообщение 10010110 становится 100101101 (четыре 1 с, дополнительный необходимый 1). Если Вы получаете сообщение 101101101 и посмотрите, что существует шесть 1 с, Вы знаете, что существует ошибка, но не знайте где. Предположим, что мы добавляем больше битов четности, каждого, на завися только от части сообщения, как проиллюстрировано ниже путем копирования битов, которые рассматривают и использования '-' для проигнорированных битов:
10110110
1-1-0-1- => 0
-0-1-1-0 => 1
10--01-- => 1
--11--10 => 0
1011---- => 0
----0110 => 1
таким образом, полное сообщение 10110110011001. Теперь предположите, что ошибка передачи изменяет третий бит в сообщении, так, чтобы это читало 10010110011001. Когда получатель повторно выполняет вычисление проверки ошибок, ему не удается соответствовать:
10010110
1-0-0-1- => 1*
-0-1-1-0 => 1
10--01-- => 1
--01--10 => 1*
1001---- => 1*
----0110 => 1
и контрольные биты, которым не удается соответствовать, являются точно теми затронутыми третьим битом данных. Это не реальная, устойчивая схема коррекции ошибок; это - просто эскиз, чтобы проиллюстрировать, как здание в дублировании может помочь в идентификации точного характера ошибки.
Вы найдете детали о способе, которым это работает здесь
Более общая информация об Ошибке Коды Corecting доступна здесь
Информация о Коде Хемминга доступна здесь и здесь.
Что касается пригодности, это объясняет почему:
Коды с коррекцией ошибок как Hamming подходят для симплексных каналов, где никакую повторную передачу нельзя требовать.
Обнаружение ошибок плюс повторная передача часто предпочитается, потому что это более эффективно.
Для сравнения рассмотрите канал с коэффициентом ошибок на бит. Позвольте размеру блока составить 1 000 битов.
Для исправления единственной ошибки (Кодом Хемминга) 10 контрольных битов за блок необходимы. Для передачи 1 000 блоков 10 000 контрольных битов (наверху) требуются. Для обнаружения единственной ошибки единственный бит четности на блок будет достаточен. Для передачи 1 000 блоков только один экс-трижды, блок (из-за коэффициента ошибок на бит) должен будет ретранслироваться, давая издержки только 2001 (= 1000 + 1001) биты.
Код Хемминга является математическим приемом для исправления до 4 потерянных битов в последовательной передаче. Это также используется в пользу "бита четности" в современных микросхемах памяти.
Ограничения находятся в числе битов, которые могут быть восстановлены, который является не больше чем 4. Если больше чем 4 бита потеряны, повторная передача требуется.
Различные ситуации требуют различных методов коррекции ошибок. Некоторые из этих методов перечислены в других сообщениях здесь.
@GameCat, а как насчет 2-битного кода обнаружения ошибок.
В этом случае допустим, что 111 изменилось на 100. Тогда мы можем быть уверены, что есть 2 неправильных бита, и мы знаем это, потому что расстояние между 111 и 100 составляет 2 бита, а расстояние между 000 и 100 составляет 1 бит. . Итак, если мы знаем, что есть 2-битная ошибка, мы можем быть уверены, что это правильное значение.