Клод Шеннон в середине прошлого века переложил энтропию термодинамики на тексты (дискретные последовательности кодов букв), что сегодня является классической основой данного направление исследований. К сожалению, для длинных чисел, например, кодов длинной в 256 бит, оценка по Шеннону требует выборки текстов огромного размера. Причина — экспоненциальная вычислительная сложность оценок энтропии по Шеннону. Одним из путей обхода экспоненциальной вычислительной сложности является переход в пространство расстояний Хэмминга по ГОСТ Р 52633.3-2011, так как в этом случае задача оценки энтропии имеет линейную вычислительную сложность. При этом результат всегда оказывается заниженным. Предложено устранить методическую погрешность, возникающую из-за вычислений в пространстве расстояний Хэмминга.
< ... >
Claude Shannon in the middle of the last century transferred the entropy of thermodynamics to texts (discrete sequences of letter codes), which today is the basis of the classics. Unfortunately, for long numbers, for example, codes 256 bits long, Shannon estimates require huge text samples. The reason is the exponential computational complexity of Shannon entropy estimates. One way to bypass exponential computational complexity is to move to the Hamming distance space according to GOST R 52633.3-2011. When moving to the Hamming distance space, the entropy estimation problem has linear computational complexity. In this case, the result always turns out to be underestimated. It is proposed to eliminate the methodological error arising from calculations in the Hamming distance space.
Keywords:
Shannon entropy, Hamming distances, probability prediction, normal distribution hypothesis
Полную версию статьи смотрите на страницах журнала «Защита информации. Инсайд»
