Browse Prior Art Database

Mask Encoding of N-Bit Strings

IP.com Disclosure Number: IPCOM000061777D
Original Publication Date: 1986-Sep-01
Included in the Prior Art Database: 2005-Mar-09
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Sinha, B: AUTHOR

Abstract

A technique is described whereby a 32-bit binary string, consisting of a substring of ones surrounded by zeros or a substring of zeros surrounded by ones, may be encoded with a minimum number of bits mask. In prior art, a typical 32-bit string consisted of either a substring of ones surrounded by zeros or a substring of zeros surrounded by ones and was encoded in eleven bits as follows: Bit 0 0 = ones surrounded by zeros 1 = zeros surrounded by ones Bits 1 - 5 Index to leftmost bit of substring Bits 6 - 10 Index to rightmost bit of substring For example, a mask field of B'10000011111" generates an all-zero mask. A mask field of B'00000011111' generates an all-one mask. Note that there is no case where the first index mask field is greater than the second index mask field; consequently, these cases are considered undefined.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 1

Mask Encoding of N-Bit Strings

A technique is described whereby a 32-bit binary string, consisting of a substring of ones surrounded by zeros or a substring of zeros surrounded by ones, may be encoded with a minimum number of bits mask. In prior art, a typical 32-bit string consisted of either a substring of ones surrounded by zeros or a substring of zeros surrounded by ones and was encoded in eleven bits as follows: Bit 0 0 = ones surrounded by zeros 1 = zeros surrounded by ones Bits 1 - 5 Index to leftmost bit of substring Bits 6 - 10 Index to rightmost bit of substring For example, a mask field of B'10000011111" generates an all-zero mask. A mask field of B'00000011111' generates an all-one mask. Note that there is no case where the first index mask field is greater than the second index mask field; consequently, these cases are considered undefined. This prior-art encoding mechanism is generally defined as follows: A string, consisting either of a substring of ones surrounded by zeros or a substring of zeros surrounded by ones may be encoded utilizing a (2n+1)-bit mask. The technique described herein improves on the efficiency of the encoded algorithm so as to minimize the number of bits needed for the encoding of n-bit strings. Given a string, the total number of possible patterns consisting of either a substring of ones surrounded by zeros or a substring of zeros surrounded by ones may be calculated as follows:

(Image Omitted)

As a result, the minimum number of bits N required to encode these patterns should be such that:

(...