Search

CN-122001528-A - Computer-aided method for solving rate-constrained vertices of symmetric multi-stage diversity coding system with linear computation

CN122001528ACN 122001528 ACN122001528 ACN 122001528ACN-122001528-A

Abstract

The invention provides a computer-aided method for solving rate constraint peaks of a symmetrical multi-stage diversity coding system with linear calculation, which is suitable for coding scheme design and rate distribution in non-ground network, multi-link broadcasting, distributed storage and other scenes. Aiming at the problems that the existing method relies on manual deduction or low-dimensional drawing and is difficult to obtain the boundary of the velocity region completely under the high-dimensional condition, the method constructs a velocity constraint inequality system by inputting the system series and the rank parameters, performs feasibility inspection, deduplication and symmetric merging on the intersection points, outputs a velocity region vertex set, and provides calculation support for reachability verification, constraint analysis and coding scheme design.

Inventors

  • Cui Ruopu
  • ZHAO SHUNING
  • Guang Xuan
  • YUAN YE

Assignees

  • 南开大学

Dates

Publication Date
20260508
Application Date
20260316

Claims (6)

  1. 1. A computer-aided method for solving rate-constrained vertices of a symmetric multi-level diversity encoding system having linear computation, comprising the steps of: S1) inputting a system level L and a rank value parameter corresponding to a coefficient vector group (v 1, v2, vL), including rk (v 1), rk ([ v1, v2 ]), rk ([ v1, vL ]); S2) recursively generating all rank valued vector sets meeting the requirement that the rank increment is 0 or 1 through buildRK (L): rk (v 1) ∈ {0,1}, and for l=2, 3..l, rk (v 1, vl) -rk ([ v1,., v_ { L-1 }) e {0,1}; S3) for each rank value vector rk, calling findBoundaryPoints (rk) to construct a corresponding rate constraint inequality system, and uniformly writing the system into a standard form A.R≤b, wherein R= (R1, the..the RL) ≡T; S4) selecting L constraint forming subsystems from the inequality set, namely if the coefficient matrix of the subsystem is full of rank, solving a linear equation to obtain a unique intersection point x, replacing x with the original inequality system, carrying out feasibility judgment by using tolerance tol=1×10-6, and reserving the intersection points meeting all constraints as vertex candidates; s5) carrying out numerical processing and structural output on the vertex candidate set, namely rounding according to tol to eliminate floating point errors, deleting repeated points, merging equivalent coordinate arrangements by utilizing symmetry, finally giving a vertex set without repeated, and converting the decimal representation into fractional representation when required.
  2. 2. The method of claim 1, wherein in step S1, the system comprises L encoders E1, E2, & gt, EL. For each k=1, 2, L there is a set of k-level decoders, each having access to any k encoder outputs and requiring the output of a corresponding linear calculation result.
  3. 3. The method of claim 2, wherein the k-level decoding objective is a linear combination of the first k sources.
  4. 4. The method according to claim 1, wherein in step S2, the linear correlation of the coefficient vector sets (v 1, v2,..vl) is described by an order, i.e. rk (v 1), rk ([ v1, v2 ]), rk ([ v1,., vL ]), for distinguishing the degree of dependency between different linear calculation requests.
  5. 5. The method according to claim 1, characterized in that in step S3, the corresponding system of rate constraint inequalities is that, when l=4, the rate constraint is given by several classes of linear inequalities, for any k e {2,3,4} and any set of encoders g_k ⊂ {1,2,3,4} of size k, there are class a constraints: Σ_{i∈G_k} R_i ≥ (k/2)·rk(v1) + (k/(2(k−1)))·rk([v1,v2]) + … + (k/4)·rk([v1,v2,v3]) + rk([v1,v2,v3,v4]) A number of class B constraints: 3R_i + Σ_{j∈G_i} R_j ≥ 3·rk(v1) + (1/2)·rk([v1,v2]) + rk([v1,v2,v3]) + rk([v1,v2,v3,v4]); 2R_i + Σ_{j∈G_i} R_j ≥ 2·rk(v1) + rk([v1,v2]) + rk([v1,v2,v3,v4]); Σ_{i=1}^4 R_i ≥ 2·rk(v1) + (2/3)·rk([v1,v2]) + (1/3)·rk([v1,v2,v3]) + rk([v1,v2,v3,v4]); r_i≥rk (v 1), R_i+R_j≥rk (v 1) +rk ([ v1, v2 ]) when i < j; Wherein g_i= {1,2,3,4} \ { i }, rk (·) represents the rank value of the corresponding set of coefficient vectors; When l=3, the rate constraint is characterized by the inequality: (1)R_i ≥ rk(v1), i=1,2,3 (2)R_i + R_j ≥ rk(v1)+rk([v1,v2]), 1≤i<j≤3 (3)R1+R2+R3 ≥ (3/2)rk(v1) + (1/2)rk([v1,v2]) + rk([v1,v2,v3]) (4)2R_i + R_j + R_k ≥ 2rk(v1)+rk([v1,v2])+rk([v1,v2,v3])。
  6. 6. The method of claim 1, wherein in step S5, rank value enumeration and symmetric merging are combined to form a reusable computing flow, and the key modules are as follows: Module M1 rank value generation (buildRK) The recursion output meets all rank sequences of a rank increment rule, outputs [0,1 ]. Times.T when L=1, expands L-1 dimension output line by line into two cases when L is more than or equal to 2, wherein the cases comprise that the rank is not increased or the rank is increased by 1; Module M2 restraint construction (constructIneqSystem D/4D) Inputting rank parameters a=rk (v 1), b=rk ([ v1, v2 ]), c=rk ([ v1, v2, v3 ]), and d=rk ([ v1, v2, v3, v4 ]) when l=4, generating inequality class by class and converting the inequality into a.r≤b; Module M3 vertex enumeration (findBoundaryPoints) Optionally L pieces of forming subsystems in all inequality, solving intersection points when the rank is full, checking whether the intersection points meet all constraints or not by using tol=1×10-6, and reserving feasible points; Module M4 numerical and structuring process And merging the equivalent arrangement by utilizing the symmetry of the encoder.

Description

Computer-aided method for solving rate-constrained vertices of symmetric multi-stage diversity coding system with linear computation Technical Field The invention belongs to the technical field of calculation auxiliary analysis related to an information theory and a coding theory, and relates to rate constraint modeling, feasible domain construction and boundary vertex solving of a symmetrical multi-stage diversity coding system under the requirement of linear calculation, in particular to a method for carrying out vertex enumeration and post-processing on a rate feasible domain described by a linear inequality group by utilizing MATLAB. Background Diversity coding systems are a typical type of multi-encoder/multi-decoder coding architecture in which the coding end maps the source into multiple coded outputs that are distributed to different nodes and the decoding end performs a reconstruction task based on the subset of coded outputs that can be accessed. The structure has natural correspondence in the scenes of distributed storage fault tolerance, satellite/multi-link broadcasting and the like. To express the recovery requirements of different priority information, the sources may be ranked by importance and introduce a "multi-level" decoding requirement that decoders with access to more encoders should be able to recover more levels (or more combinations) of information. The symmetric multi-level diversity coding system further introduces the assumption of symmetry that the same level of decoder can access any same number of encoder outputs. In applications such as non-terrestrial networks (e.g., multi-satellite/multi-link non-terrestrial communication systems), the receiving end is often concerned with a specific function of several sources of information rather than the entire source itself. To characterize such a requirement, the decoding objective can be replaced by "compute linear combinations" from the "recovery source" to form a symmetric multi-level diversity coding system (SMDCS-LC) with linear computation requirements. The system schematic can be referred to fig. 1 and 2. In rate area analysis of SMDCS-LCs, constraints are often written as a set of linear inequalities, abstracting the achievable rate set into a convex polyhedron (or approximation thereof) in high-dimensional space. When the dimension is raised (e.g., l=4), it is difficult to obtain the boundary structure entirely by means of geometric mapping alone, and it is particularly difficult to systematically enumerate all vertices. To solve this problem, a reusable computational flow is needed to normalize the constraint system to a matrix inequality form and obtain the vertex set by "subsystem intersection + feasibility screening + deduplication/symmetric processing". Disclosure of Invention The invention aims to provide a SMDCS-LC rate constraint analysis-oriented computer-aided solving method, which automatically builds a rate constraint inequality system and obtains all vertexes of a feasible domain under the condition of given system series L and coefficient vector rank value, so as to provide a stable and repeatable calculating tool for rate constraint verification, rate region boundary depiction and subsequent constraint revision. In order to achieve the above purpose, the invention adopts the following technical scheme: A computer-aided method for solving rate-constrained vertices of a symmetric multi-level diversity coding system with linear computation, comprising the steps of: S1) inputting a system level L and a rank value parameter corresponding to a coefficient vector group (v 1, v2, vL), including rk (v 1), rk ([ v1, v2 ]), rk ([ v1, vL ]); S2) recursively generating all rank valued vector sets meeting the requirement that the rank increment is 0 or 1 through buildRK (L): rk (v 1) ∈ {0,1}, and for l=2, 3..l, rk (v 1, vl) -rk ([ v1,., v_ { L-1 }) e {0,1}; S3) for each rank value vector rk, calling findBoundaryPoints (rk) to construct a corresponding rate constraint inequality system, and uniformly writing the system into a standard form A.R≤b, wherein R= (R1, the..the RL) ≡T; S4) selecting L constraint forming subsystems from the inequality set, namely if the coefficient matrix of the subsystem is full of rank, solving a linear equation to obtain a unique intersection point x, replacing x with the original inequality system, carrying out feasibility judgment by using tolerance tol=1×10-6, and reserving the intersection points meeting all constraints as vertex candidates; s5) carrying out numerical processing and structural output on the vertex candidate set, namely rounding according to tol to eliminate floating point errors, deleting repeated points, merging equivalent coordinate arrangements by utilizing symmetry, finally giving a vertex set without repeated, and converting the decimal representation into fractional representation when required. Further, in step S1 of the present invention, the system comprises L encoder