Late on Friday, an administrative law judge of the US International Trade Commission issued a determination that HTC’s Android-based devices infringe two Apple patents. This decision is not yet final, but if affirmed, HTC faces an import ban against its products in the U.S. market before the end of the year. I said on Twitter that in this scenario, HTC’s Android U.S. market share in 2012 would be 0.0%. I furthermore pointed out that those patents are also asserted against Motorola and I think it’s very likely that all Android devices infringe them.

Deep down in the ITC archives I’ve dug up the so-called infringement claim charts Apple presented to the ITC in its dispute with HTC. Infringement claim charts, or often just called “claim charts”, typically show the language of a patent claim on the left side and a description of the infringing activity on the right side. Any given patent claim is only infringed if all of the characterizations on the left side are matched by (accurate) information on the right side.

HTC vowed to fight on and claimed that it has “alternate solutions”. But can those patents really be worked around? Standing in front of the Great Wall of China, you can also vow to walk around it. That doesn’t mean it’s a viable option.

Note that the language of those claim charts often appears to indicate that the asserted infringement is proven for only one device. But Apple accused all Android-based HTC products in its complaint, and if a claim chart refers to one particular device, then it’s just an “exemplary” claim chart and not an exhaustive one. The ruling will ultimately affect all products that have the same (or materially the same) infringement pattern.

Infringement claim chart for the ‘647 patent (action-on-data-structure patent)

U.S. Patent No. 5,946,647 covers a “system and method for performing an action on a structure in computer-generated data”. Like most patents, this one consists of multiple claims. In a way, each patent claim is like a patent of its own when it comes to the question of infringement. The ITC judge found that the accused HTC products infringe claims 1, 8, 15 and 19 of that patent. If you see that claim 1 of a given patent is infringed, that means in most cases that the broadest claim in the patent — or at least one of its broadest few claims — is infringed. (Those are the kinds of claims that can be as easy to walk around as the Great Wall of China.)

In its complaint, Apple described this patent (which was applied for back in 1996 and which will expire on February 1, 2016) as follows:

The ‘647 patent generally relates to a computer-based system and method for detecting structures and performing computer-based actions on the detected structures. In particular, this invention recognizes that computer data may contain structures, for example, phone numbers, post-office addresses, and dates, and performs related actions with that data. The ‘647 patent accomplishes this by identifying the structure, associating candidate actions to the structures, enabling selections of an action, and automatically performing the selected action on the structure. For instance, the system may receive data that includes a phone number, highlight it for a user, and then, in response to a user’s interaction with the highlighted text, offer the user the choice of making a phone call to the number.

Fortune.CNN.com’s Apple expert Philip Elmer-DeWitt shows a picture of an iPhone and explains what functions one can perform on that screen that are covered by the ‘647 patent.

Here’s now the table that juxtaposes the language of claim 1 of the patent and Android’s infringing behavior:

Claims	Accused HTC Android Products
1. A computer-based system for detecting structures in data and performing actions based on detected structures, comprising:an input device for receiving data;	The Accused HTC Android Products contain a computer-based system for detecting structures in data and performing actions based on detecting structures, and comprises an input device for receiving data. For instance, the HTC Nexus One contains a 3.7 inch AMOLED touchscreen. (Ex. 26-A, Nexus One User Manual at 327.) The Nexus One thus includes an input device to receive computer data, from which it will detect structures, such as phone numbers and email addresses, in data such as email and SMS messages. (Ex. 26-A, Nexus One User Manual at 208.) By way of example, the functionality within the Nexus One includes Android’s “Linkify” functionality, which “take[s] a piece of text and a regular expression and turns all of the regex matches in the text into clickable links. This is particularly useful for matching things like email addresses, web urls, etc. and making them actionable.” (Ex. 26-B, Android Developer Site at Linkify.java) In particular, the matching functionality within Android’s “Linkify” engine searches text strings for structures representative of Web URLs, phone numbers, email addresses, and map addresses. (Id.)
an output device for presenting the data;	The Accused HTC Android Products contain an output device for presenting the data. For instance, the HTC Nexus One contains a 3.7 inch WVGA AMOLED touchscreen that serves as an output device. (Ex. 26-A, Nexus One User Manual at 327.)
a memory storing information including program routines including	The Accused HTC Android Products contain a memory storing information including program routines. For instance, the HTC Nexus One contains 512MB of Flash memory, which stores program routines, including the phone’s Android operating system and applications on the phone. (Ex 26-A” Nexus One User Manual at 327; see also id. at 318.)
an analyzer server for detecting structures in the data and for linking actions to the detected structures;	The Accused HTC Android Products contain at least one analyzer server for detecting structures in the data and for linking actions to the detected structures. For example, the Nexus One includes an analyzer server that detects structures, such as phone numbers and email addresses, in data such as email and SMS messages. (Ex. 26-A, Nexus One User Manual at 208.) By way of example, the analyzer server within the Nexus One includes Android’s “Linkify” functionality, which “take[s] a piece of text and a regular expression and turns all of the regex matches in the text into clickable links. This is particularly useful for matching things like email addresses, web urls, etc. and making them actionable.” (Ex. 26-B, Android Developer Site at Linkify.java.) In particular, the matching functionality within Android’s “Linkify” engine searches text strings for structures representative of Web URLs, phone numbers, email addresses, and map addresses. (Id.)
a user interface enabling the selection of a detected structure and a linked action; and	The Accused HTC Android products contain a user interface enabling the selection of a detected structure and a linked action. For example, the Nexus One contains applications for browsing the Internet and for viewing email messages or conversation histories. These applications provide a user interface that allows the user to select a detected structure and a linked action. For instance, the Nexus One’s “Browser” application will cause all phone numbers found in a web page to be “linkable” to the user – that is, they will be highlighted and underlined. The user may then select a phone number by tapping on it, which will cause a linked action, such as sending the number to the Phone application, to occur. (See Ex 26-A, Nexus One User Manual, page 208.)
an action processor for performing the selected action linked to the selected structure; and	The Accused HTC Android products contain an action processor for performing the selected action linked to the selected structure.For example, when a user clicks on a linked a phone number in the Nexus One’s “Browser” application, the Nexus One will launch the “Phone” application and import the selected phone number into the Phone application. (Ex. 26-A” Nexus One User Manual at 78; see also id. at 208.)
a processing unit coupled to the input device, the output device, and the memory for controlling the execution of the program routines.	The Accused HTC Android products contain a processing unit coupled to the input device, the output device, and the memory for controlling the execution of the program routines. For example, the Nexus One contains a Qualcomm QSD 8250 “Snapdragon” 1 GHz processor that controls the execution of the program routines. (Ex. 26-A, Nexus One User Manual at 327.)

Apple’s exemplary claim chart for this patent also covers other claims than claim 1, including claim 15, which is another one of those claims of the patent that the ITC judge found HTC to infringe. Note that HTC can only avoid an import ban if it defeats all asserted patent claims.

Claims	Accused HTC Android Products
In a computer having a memory storing actions, a method for causing the computer to perform an action on a structure identified in computer data, comprising the stops of:receiving computer data	The Accused HTC Android Products are computers that have a memory storing actions, and perform a method for causing the computer to perform an action on a structure identified in computer data, comprising the step of receiving computer data.For instance, the HTC Nexus One contains 512MB of Flash memory, which stores program routines, including the phone’s Android operating system and applications on the phone. (Ex 26-A, Nexus One User Manual at 327; see also id. at 318.) Additionally, the Nexus One contains a Qualcomm QSD 8250 “Snapdragon” 1 GHz processor that controls the execution of the program routines. (Ex. 26-A, Nexus One User Manual at 327.) The Nexus One includes functionality to receive computer data, from which it will detect structures, such as phone numbers and email addresses, in data such as email and SMS messages. (Ex. 26-A, Nexus One User Manual at 208.) By way of example, the functionality within the Nexus One includes Android’s “Linkify” functionality, which “take[s] a piece of text and a regular expression and turns all of the regex matches in the text into clickable links. This is particularly useful for matching things like email addresses, web urIs, etc. and making them actionable.” (Ex. 26-B, Android Developer Site at Linkify .java) In particular, the matching functionality within Android’s “Linkify” engine searches text strings for structures representative of Web URLs, phone numbers, email addresses, and map addresses. (Id.)
detecting a structure in the data;	The Accused HTC Android Products perform the step of detecting a structure in the data. For example, the Nexus One includes a means that detects structures, such as phone numbers and email addresses, in data such as email and SMS messages. (Ex. 26-A, Nexus One User Manual at 208.) By way of example, the means within the Nexus One includes Android’s “Linkify” functionality, which “take[s] a piece of text and a regular expression and turns all of the regex matches in the text into clickable links. This is particularly useful for matching things like email addresses, web urls, etc. and making them actionable.” (Ex. 26-B, Android Developer Site at Linkify.java) In particular, the matching functionality within Android’s “Linkify” engine searches text strings for structures representative of Web URLs, phone numbers, email addresses, and map addresses. (Id.)
linking at least one action to the detected structure;	The Accused HTC Android Products perform the step of linking at least one action to the detected structure. For example, the Nexus One contains applications for browsing the Internet and for viewing email messages or conversation histories. These applications provide a user interface that allows the user to select a detected structure and a linked action. For instance, the Nexus One’s “Browser” application will cause all phone numbers found in a webpage to be “linkable” to the user that is, they will be highlighted and underlined. The user may then select a phone number by tapping on it, which will cause a linked action, such as sending the number to the Phone application, to occur. (See Ex. 26-A, Nexus One User Manual, page 208.)
enabling selection of the structure and a linked action; and	The Accused HTC Android Products perform the step of enabling selection of the structure and a linked action. For example, the Nexus One contains applications for browsing the Internet and for viewing email messages or conversation histories. These applications provide a user interface that allows the user to select a detected structure and a linked action. For instance, the Nexus One’s “Browser” application will cause all phone numbers found in a webpage to be “linkable” to the user – that is, they will be highlighted and underlined. The user may then select a phone number by tapping on it, which will cause a linked action, such as sending the number to the Phone application, to occur. (See Ex. 26-A,Nexus One User Manual, page 208.)
executing the selected action linked to the selected structure	The Accused HTC Android Products perform the step of executing the selected action linked to the selected structure. For example, when a user clicks on a linked phone number in the Nexus One’s “Browser” application, the Nexus One will launch the “Phone” application and import the selected phone number into the Phone application.

Apple’s exemplary claim charts for this patent don’t discuss the other claims that the ITC judge found HTC to infringe as well. But the two examples above make it pretty clear what the patent relates to. This is about Android’s “Linkify” functionality. It’s most probably built into each and every Android device out there.

Infringement claim chart for the ‘263 patent (real-time signal processing API patent)

U.S. Patent No. 6,343, 263 covers a “real-time signal processing system for serially transmitted data”. Like most patents, this one consists of multiple claims. In a way, each patent claim is like a patent of its own when it comes to the question of infringement. The ITC judge found that the accused HTC products infringe claims 1, 2, 24 and 29 of that patent.

In its complaint, Apple described this patent (which was applied for back in 1994 and which will expire on January 29, 2019) as follows:

The ‘263 patent relates generally to providing programming abstraction layers for real-time processing applications. The ‘263 patent discloses the use of real-time application programming interfaces (APIs) interposed between application software or driver software and the real-time processing subsystem. These APIs provide an abstraction for the real-time processing subsystem (e.g., a digital signal processor) from the higher-level software that utilizes the real-time processing subsystem, allowing changes to the real-time processing subsystem without requiring changes to the higher-level software.

So while the title “real-time signal processing system” might have suggested a hardware patent at first, this is actually an API patent, and therefore, a software patent.

This patent is probably another one that’s extremely hard to work around. In Android’s case, it’s possible that working around this patent requires a fundamental change to Android’s architecture, and possibly even to the architecture of the underlying Linux kernel.

Apple’s exemplary claim chart discusses claims 1 and 3. Of those two claims, HTC was found to infringe claim 1 and three others that the claim chart does not relate to. So here’s the infringement claim chart for claim 1:

Claim 1	Accused HTC Android Products
1. A signal processing system for providing a plurality of realtime services to and from a number of independent client applications and devices, said system comprising:	The Accused HTC Android Products, including the HTC Nexus One, are devices which comprise a signal processing system for providing a plurality of realtime services to and from a number of independent client applications and devices. For example, the HTC Nexus One is based on the Qualcomm QSD 8250 chip, which uses a 1 GHz CPU. (Ex. 29-A, Nexus One Specification). Qualcomm’s QSD 8250 chipset provides a variety of real-time services such as audio and video processing. (Ex. 29-B, Snapdragon, Qualcomm Snapdragon, QCT Snapdragon, – QTConnect.com)
a subsystem comprising a host central processing unit (CPU) operating in accordance with at least one application program and a device handler program, said subsystem further comprising an adapter subsystem interoperating with said host CPU and said device;	The Accused HTC Android Products include a subsystem comprising a host CPU operating in accordance with at least one application program and a device handler program. For example, the HTC Nexus One uses a 1 GHz CPU for executing audio and video application programs, and device handler programs. (Id.) On information and belief, the HTC Nexus One includes audio and video adapters interoperating with the core CPU. (Id.)
a realtime signal processing subsystem for performing a plurality of data transforms comprising a plurality of realtime signal processing operations; and	The Accused HTC Android Products, including the HTC Nexus One, include a realtime signal processing subsystem for performing a plurality of data transforms comprising realtime signal processing operations. For example, the QSD 8250 contains a digital signal processor for realtime signal processing and also provides a variety of realtime signal processing operations such as audio and video processing. (Id.)
at least one realtime application program interface (API) coupled between the subsystem and the realtime signal processing subsystem to allow the subsystem to interoperate with said realtime services.	The Accused HTC Android Products include at least one realtime API coupled between the subsystem and the realtime signal processing subsystem. On information and belief, the HTC Nexus One kernel source code defines an API coupled between the subsystem comprising the host CPU and the real-time processing subsystem (i.e., the DSP processor).

Given the potential of the above infringement claim charts to result in a ban of HTC’s Android-based products from the U.S. market within about four months, I’m sure there’ll be quite some discussion of those patents and of the Android-related infringement allegations.

If you’d like to be updated on the smartphone patent disputes and other intellectual property matters I cover, please subscribe to my RSS feed (in the right-hand column) and/or follow me on Twitter @FOSSpatents.