Methods and apparatuses for encoding and decoding a bytestream

Patent metadata

Field	Value
Publication number	US-11632560-B2
Application number	US-201816769803-A
Country	US
Kind code	B2
Filing date	Dec 6, 2018
Priority date	Dec 6, 2017
Publication date	Apr 18, 2023
Grant date	Apr 18, 2023

Abstract

There is provided a method of decoding a received set of encoded data, the method comprising: receiving an encoded dataset; identifying from the dataset an ordered set of node symbols and data symbols, wherein a node symbol comprises a predetermined number of elements wherein each element indicates if a subsequent node symbol or data symbol is to be expected in the dataset and a data symbol is a predetermined number of bits which represent an encoded value; constructing, based on said ordered set, an ordered tree having a predetermined number of layers from the identified node symbols and data symbols.

First claim

The invention claimed is:

1. A method of decoding a received set of encoded data, the method comprising:
receiving an encoded dataset usable to construct an ordered tree, wherein the ordered tree comprises a root and a plurality of layers, each layer being associated with a respective distance from the root, and wherein a layer associated with a largest distance from the root comprises all leaf nodes of the ordered tree, the encoded dataset comprising:
one or more node symbols; and
one or more data symbols, the one or more node symbols and the one or more data symbols forming an ordered set of node symbols and data symbols in the encoded dataset, wherein:
a node symbol comprises a predetermined number of elements, wherein each element indicates whether or not subsequent portions of the ordered set of node symbols and data symbols in the encoded dataset contain information for one or more nodes of the ordered tree, and wherein the one or more nodes symbols indicate which leaf nodes of the layer associated with the largest distance from the root of the ordered tree will include encoded values represented by data symbols of the ordered set, and
a data symbol comprises a predetermined number of bits which represent an encoded value for one or more leaf nodes of the layer associated with the largest distance from the root of the ordered tree, wherein order of the one or more data symbols within the ordered set determines locations of leaf nodes of the layer associated with the largest distance from the root of the ordered tree for encoded values represented by the one or more data symbols; and

constructing, based on said ordered set, the ordered tree having a predetermined number of layers from the one or more node symbols and the one or more data symbols, wherein the ordered tree comprises, for leaf nodes of the layer associated with the largest distance from the root of the ordered tree indicated by the one or more node symbols as including encoded values represented by data symbols of the ordered set, encoded values of the one or more data symbols at the locations determined by the order of the one or more data symbols within the ordered set.

2. The method of claim 1 , wherein constructing the ordered tree comprises:
retrieving a first node symbol from the encoded dataset; and
associating the first node symbol with a first node of the tree and associating each element of the first node symbol with a branch node of the first node.

3. The method of claim 2 , wherein if the associated element for a branch node indicates a subsequent node symbol exists in the encoded dataset for the branch node, the method further comprises traversing the tree 20 by:
retrieving a subsequent node symbol from the ordered set;
associating the subsequent node symbol with the branch node; and,
associating each element of the subsequent node symbol with a respective subbranch node for the branch node.

4. The method of claim 2 , wherein if the associated element for a branch node indicates no subsequent node symbol exists in the encoded dataset for the branch node, the method further comprises terminating traversal of the tree for that branch node.

5. The method of claim 2 , wherein if the branch node is a node whose children would be data nodes, traversing the tree further comprises retrieving a data symbol from the set.

6. The method according to claim 4 , further comprising:
simulating a sub-tree after terminating the traversal, wherein the sub-tree comprises data nodes whose data symbols have a predetermined value.

7. The method according to claim 1 , further comprising:
mapping each leaf node of the layer associated with the largest distance from the root of the ordered tree into an array having at least two dimensions.

8. The method of claim 1 , wherein the ordered tree comprises a predetermined value for nodes of the ordered tree for which the one or more node symbols indicate that subsequent portions of the encoded dataset contain no information.

Assignees

• V Nova Int Ltd

Inventors

• Makeev Ivan
• Keszthelyi Balázs
• Poularakis Stergios
• Sanna Michele
• Ettinger Robert

Classifications

• H04L65/756

  adapting media to device capabilities · CPC title

• H04N19/44 Primary

  Decoders specially adapted therefor, e.g. video decoders which are asymmetric with respect to the encoder · CPC title

• H04N19/96 Primary

  Tree coding, e.g. quad-tree coding · CPC title

• H04N19/13

  Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC] · CPC title

• G06F17/16

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title