IEEE Consumer Electronics Magazine - April 2017 - 120

ters used for register allocation based
on Figure 4.
Register 1

Register 2

V0

(R)

(R)

*

(M 1)
(R)

+

(A1)
(R)

*

(M 1)
(R)

+

(A1)
(R)

V4

(R)

+

(A3)

(G)

*

(M 2)

V8

(G)

+

(A2)
(G)

V 11
(M 2)

*

V 2 (Y)

(B)

(B)
V5
(M 3)

Register 4

(Y)

*

V6
(M 4)

(Y)
V9

(Y)

V 12

(M 3)

V 14

DESIRED SIGNATURE SELECTION
AND EMBEDDING WATERMARK

V3

*

V7

+

V10

(A3)

(Y)

*

V13

+

V 15

(A1)

1

2

3

4

5

*

V 16

V1

(G)

Register 3

(M 4)

Register_R

6

V17

Register_P

FIGURE 3. A scheduled graph with allocation (without a watermark). R: red; G: green;
B: blue; Y: yellow.

Table 1. A timing table for register allocation before embedding
the watermark.
Control Step

Red

Green

Blue

Yellow

0

V0

V1

V2

V3

1

V4

V5

V6

V7

2

V8

V9

V6

V10

3

V11

V12

-

V13

4

V14

V12

-

V15

5

V16

V12

-

V15

6

V17

-

-

V15

overlapping. Figure 4 shows the
colored interval graph for the storage
variables (V0-V17) shown in Figure 3.
120 IEEE Consumer Electronics Magazine

^

april 2017

The corresponding timing table for
the register allocation of storage variables (Table 1) provides the five regis-

Once the initial colored interval graph
and timing table for register allocation
are generated, the next step is to select
a desired signature based on the multivariable encoding of I, i, !, and T. The
encoded meaning of each of the variables follows [4], [5]:
▼▼ i: encoded value of edge with node
pair as (prime, prime)
▼▼ I: encoded value of edge with node
pair as (even, even)
▼▼ T: encoded value of edge with node
pair as (odd, even)
▼▼ !: encoded value of edge with node
pair as (0, any integer).
Let us select a seven-digit signature:
i i I I T T!. After converting this desired
signature to watermarking constraints,
the representation is shown in Table 2.
These are the extra edges between nodes
(acting as watermarking constraints) that
we need to insert into the colored interval graph. Adding extra edges between
nodes as per watermarking constraints
forces the storage variables (nodes of the
graph) to be assigned to distinct registers. In other words, due to the addition
of watermarking constraints, the register
assignments change.
The modified colored interval graph
with inclusion of watermarking constraints (extra edges) is shown in Figure 5.
Few extra edges were already added by
default; thus, they cannot be added. The
remaining ones are inserted (in dotted
lines). The corresponding timing table
for the modified register allocation
based on these forced distinct register
assignments is shown in Table 3. The
register allocation change due to inserting watermarking constraints is also
reflected in the scheduling graph. The
modified graph with a new register allocation is shown in Figure 6.

DEVELOPMENT OF MULTIPLEXING
SCHEMES FROM SCHEDULE/
ALLOCATION GRAPH
For each of the resources/hardware and
registers allocated (i.e., three adders,
four multipliers, and five registers), a
Table of Contents for the Digital Edition of IEEE Consumer Electronics Magazine - April 2017
