How can I identify the usage implications of this granted patent for the base91 encoding algorithm?

Question

I'm currently doing some research on base-n binary encoding algorithms (such as base32, base58, base64, base85, base91, etc) to see if the tradeoff between complexity (base64 implementations are ubiquitous due to email and JavaScript; others not so much) and performance (bigger base = slightly more efficient) is worth the effort.

While base91 seems to have really good properties for my requirements, I just found patent US20030152220A1, which looks like it fairly concretely captures the implementational specifics of base-n encoding, and base91 in particular. (Indeed, the patent actually answers some questions I had about the specifics of implementing base91!)

So, I'm very curious. base91 isn't widely implemented, but it isn't that hard to find open-source Perl, Python, PHP, C#, C, and even assembly-language implementations out there, so people are using it. I'm sure it's implemented commercially too.

I understand that patents only grant someone the right to enforce their ownership of something. With this in mind, is there an easy way I can find out that using base91 may be a Bad Idea™?

As an example of the standpoint I'm coming from, the H.264 video format is patented, and while there are open-source H.264 codecs that permit royalty-free commercial use (eg via the LGPL), it's generally a good idea to get eg a patent pool license from MPEG-LA when actually using H.264 in a commercial setting, as the H.264 patents do not permit royalty-free commercial use.

This base91 patent only covers the technical specifics and does not stipulate any royalties or other requirements, and furthermore I've never heard of any patent issues with any base-n encoding scheme. However, this patent was granted, to a university in China (effective Nov 2002 forward), and I'd like to stay on the safe side.

That said, I really don't want the answer to be "don't use it" :)

My apologies if this question is formatted incorrectly or is inappropriate for this site. First question here! :)
(I also suspect I'm not using the best tags for this question.)

---

Technical aside for anyone curious: Wikipedia's entry for base64 provides a decent explanation that explains the algorithm reasonably accessibly. Essentially, many situations that require binary data to be passed through systems that cannot safely handle binary data (most notably email, for historical reasons) generally encode the data using base64.

Answer 1

You cited a patent application rather than a granted patent. The granted patent corresponding to the application is US6859151B. Granted patents often have narrower claims than applications. Here is the first claim:

1. A coding transformation method, used to transform an arbitrary input bit-string data into a sequence of printable ASCII characters, the coding transformation being implemented by the computer software, characterized in:

   (a) storing an executable program module to be used to execute the coding transformation into the program storage of the computer system, and building the output character set R91_CH[91] in the computer memory and filling in the table of the bit denoting array φ[13];

   (b) makes the input byte-string pointer pointing to a starting address of the byte-string to be coded, recording the length of the byte-string to be coded by using a variable, make the program counting pointer pointing to the entry address of a previously described executable program module in the program storage, reading the instruction and executing coding transformation;

   (c) the coding transformation divides the input data into blocks with the length of 13 bits,

   (d) for the coding transformation of blocks, the variable set or the original image set X includes all 8192 13-bit symbols and 12 filling-bit denoting symbols φ1, . . . , φ12, totally amounting to 8204 elements;

   (e) using 91 or 92 (considering the terminating symbol “=”) printable ASCII characters in the output representation of the coding transformation,

   (f) for the coding transformation of blocks, the image set Y is the sub-set of the direct product R91×R91, wherein R91 is the set of 91 printable characters, in particular R91 excluding printable ASCII characters “−” and “=”, the reversible coding mapping relationship is

   Base91[x]=(ch1, ch2)=(R91— CH[x/91], R91— CH[x%91]) wherein xεX, ch1, ch2εR91, symbols “/” and “%” are the operators used in the C language, representing integral division and modulo division (remainder) respectively;

   (g) for the input data block less than 13-bit long, adding n bits to the specified side to make it become a complete block for implementing mapping, thereafter adding a block of data φn as the input data block implementing mapping, its image is in the direct product R91×R91.

This seems to be a pretty long and detailed claim. Generally speaking longer claims are easier to avoid than short ones. In order to infringe on this claim, you have to perform each and every step of the claim. For instance, step (c) specifies blocks of 13 bits. Using a different length block would possibly avoid infringement. There are two more independent claims that are similarly long and detailed. I'm not really knowledgable in this field so I hesitate to comment further, but carefully read the claims of the issued patent to see how restrictive this patent really is.