Хеширование 48-битного ключа в 16-битное значение

Я работаю с устройствами, которые получают очень маленькие пакеты данных. Устройство уникально идентифицировано с помощью 48-битного ключа. Когда устройство получает отдельный пакет, ему необходимо прочитать пакет и определить, был ли пакет предназначен для этого устройства. Звучит просто, но пакет имеет достаточно места только для 16-битного ключа.Хеширование 48-битного ключа в 16-битное значение

Протокол связи не может быть изменен. Я не могу использовать несколько пакетов или любые другие поля в пакете. В основном мне нужно сохранить этот 48-битный идентификатор в 16-битном поле. Очевидно, что будут столкновения с любым решением.

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

PS: На самом деле это похоже на то, что первые три байта исходного ключа всегда одинаковы, поэтому эта проблема просто сводилась к перетаскиванию 24-битного ключа в 16-битный ключ, но все же неплохо.

PPS: Столкновения не являются катастрофическими. Устройство может восстанавливаться, но оно дорого.

источник

2013-11-27 vopilif

«* Каков наилучший способ сделать это при минимизации столкновений?» «Это невозможно ответить, не зная о назначении и распределении используемых значений. – RBarryYoung

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

Являются ли отдельные устройства программируемыми? Можете ли вы настроить устройство, чтобы сообщить ему, что его 16-битный ключ? Если вы знаете все идентификаторы устройств спереди, вы можете создать [минимальный совершенный хеш] (http://en.wikipedia.org/wiki/Perfect_hash_function#Minimal_perfect_hash_function). Но, не указав устройству на поиск определенных номеров пакетов, вероятность столкновения будет отличной от нуля. –

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

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

источник

2013-11-27 12:32:39

Единственная вещь, которая может вам помочь в этой ситуации, - это если у вас есть устройства менее или равные 2^16. здесь вам нужно иметь хеш-таблицу, которая отображает каждый ключ 24-bit на уникальный ключ 16-bit. Поэтому при отправке пакета отправьте 16-bit ключ и в то же время извлекая проверку для сопоставленного ключа в хэш-таблице. Вы также можете жестко скопировать значения ключей 16-bit для прямых сравнений. Но если у вас есть более 2^16 устройств, то в соответствии с принципом голубого отверстия у вас будет 2 или более устройства с одним и тем же ключом 16-bit, тогда вы не можете быть уверены, какое устройство предназначено для этого пакета.

Псевдо код для отправки & приема пакета: -

Send(BigKey,Data) { 

    // get 16-bit key from 24-bit one 
    SmallKey = HashMap.getValue(BigKey); 
    Packet = SmallKey + Data ; 

} 

Receive(Packet) { 

    (Key,Data) = split(Packet); 

    // get devices 16-bit key 
    SmallKey = HashMap.getValue(MyKey); 

    if(SmallKey==Key) 
     Process(Data) 
    else Error("Invalid Packet"); 

}

Примечание: - карта Хеш может быть создан с использованием красно-черные деревья, Б-дерево и т.д., которые вы поиск в O (LogN). который достаточно хорош для вашего приложения здесь.

источник

2013-11-27 05:51:03

Хеширование 48-битного ключа в 16-битное значение

ответ

Смежные вопросы