text:
A bit of everything

# Warp drives

Superluminal travel in general relativity, or warp drives, are roughly defined by the (local) change of distances between two points on some initial spacelike hypersurface. The classic example being, if we consider flat spacetime

$$ds^2 = -dt^2 + dx^2 + dy^2 + dz^2$$

and consider the distance from Earth to Alpha Centauri (roughly $4.37\ \text{ly}$), with no proper motion from the two points, we want to change the metric to reduce the distance between those two points, that is, the proper time a timelike curve (or causal curve, if it is a signal) will take to reach it.

$$d(\oplus, \odot_{\alpha}) = \int_{\oplus}^{\odot_\alpha} (g(\dot u, \dot u))^{\frac{1}{2}} d\tau \ll 4.37\ \text{ly}$$

Ideally the time taken should also be small from the point of view of a stationary observer on Earth. That is, for a two way trip from Earth to Alpha Centauri and back to Earth, we want an observer on Earth to wait

$$\Delta \tau =$$

We'll also ask that the metric modification be local, that is, the original flat spacetime has a spacelike hypersurface $\Sigma$ such that $\Sigma \setminus K$, $K$ a compact set, is isometric to our new spacetime.

## 1. Warp drives, faster-than-light spacetimes and spacetime shortcuts

Defining what qualifies as a warp drive isn't quite easy, since it depends on the future structure of the metric, and it is easy to make it too broad. Simply passing through a gravitational well is enough to reduce the proper time of a trip, but while it could be used to reduce travel time, it seems odd to call it a warp drive. The original Alcubierre warp drive itself is in fact inspired by the FLRW cosmological metric, where the expansion of the universe can cause two points to get separated at speeds greater than the speed of light.

To define it properly, here are some definitions due to Krasnikov[3][4] :

First, we take $\mathcal{M}_1$ and $\mathcal{M}_2$ two spacetimes with inextendible timelike curves $\mathcal E_i, \mathcal D_i \subset \mathcal M_i$, $i = 1,2$ ($\mathcal E$ is the curve of Earth while $\mathcal D$ is the curve of the destination), define $S_i \in \mathcal E_i$ (the point at which a spaceship departs from Earth), with the two following points \begin{eqnarray} F_i &=& \operatorname{Bd}(J^+(S_i)) \cap \mathcal D_i\\ R_i &=& \operatorname{Bd}(J^+(F_i)) \cap \mathcal E_i \end{eqnarray}

$F_i$ is the lower bound to the arrival of a signal at the destination $D_i$, while $R_i$ is the lower bound for the return of a signal to $E_i$. The difference in proper time between $S_i$ and $R_i$ will then be the lower bound for any signal to take the full trip from $E$ to $D$ and back.

If we have $N_i \subset M_i$, with $N_1$, $N_2$ related by an isometry $N_2 = \phi(N_1)$, we note $A \star B$ if either $A$ and $B$ belong to the same manifold and $A = B$, or if $$\lim a_i = A \to \lim \phi(a_i) = B$$

## 2. The basic idea

All faster-than-light metrics use the same basic trick, which is to locally widen the light cone to permit, from the perspective of an observer at rest, to go faster than light. The exact method for this will vary, but if we consider 2D Minkowski space, it will always look locally like something of the form \begin{eqnarray} ds^2 &=& (k_l dx - dt)(k_r dx + dt)\\ &=& -dt^2 - (k_r + k_l) dt dx + k_l k_r dx^2 \end{eqnarray}

For this metric, we get, for a null vector $(u_t, u_x)$,

$$-u_t^2 - (k_r + k_l) u_t u_x + k_l k_r u_x^2 = 0$$ With solution $$u_t = u_x \left[ -\frac{(k_r + k_l)}{2} \pm \frac{\sqrt{ (k_r + k_l)^2 + 4 k_l k_r}}{2} \right]$$ For $k_l = k_r = k$ $$u_t = u_x (-1 \pm \sqrt{2})k$$

## 3. The Alcubierre warp drive metric

The basic idea behind the Alcubierre warp drive metric is to locally widen the light-cone, so that an object inside that region will appear to go faster than light to an observer with a normal light-cone.

\begin{eqnarray} ds^2 &=& -dt^2 + (dx - v_s f(r_s)dt)^2 + dy^2 + dz^2 \\ &=& -(1 - v_s^2 f^2(r_s))dt^2 - 2 v_s f(r_s) dx dt + dx^2 + dy^2 + dz^2 \end{eqnarray}

This metric depends on a (not necessarily causal) curve $x_s(t)$, which gives rise to the velocity of the warp bubble

$$v_s(t) = \frac{dx_s(t)}{dt}$$

$$r_s(t) = [(x - x_s(t))^2 + y^2 + z^2]^{\frac 12}$$

Due to the way the metric is constructed, the curve $x_s(t)$ cannot be arbitrary. If an initially "future directed" $C^1$ curve (that is, with tangent $(u_t, u_x)$, with $u_t > 0$) approaches the tangent vector $(0, 1)$, the velocity of the warp bubble will diverge as

The function $f$ is simply some function to separate the inside and the outside of the "warp bubble". If it's a spherical bubble of radius $R$, it will be of the form

$$f(r_s) = \begin{cases} \approx 1 & r_s \ll R\\ \approx 0 & r_s \gg R \end{cases}$$

In other words, the spacetime should be approximately Minkowski space far from the bubble, and the desired metric well inside the bubble. It can for instance some bump function or just a rapidly decaying function, such as in the original Alcubierre paper :

$$f(r_s) = \frac{\tanh(\sigma (r_s + R)) - \tanh(\sigma (r_s - R))}{2\tanh(\sigma R)}$$

Assuming a bump function that is $0$ outside the bubble and $1$ inside some radius, the spacelike hypersurface on the $(x,y)$ plane decomposes like this

The lightcones representing what happens in the timelike direction.

Both inside and outside the bubble, the metric is just Minkowski space, but with a different slant to the light cone. Well inside the bubble, the metric is just

\begin{eqnarray} ds^2 &=& -dt^2 + (dx - v_s dt)^2 + dy^2 + dz^2\\ &=& - (1 - v_s^2) dt^2 - 2 v_s dxdt + dx^2 + dy^2 + dz^2 \end{eqnarray}

This has the metric determinant $- 1$, which is always negative, meaning that the spacetime is valid for any value of $v_s$. The effects on the lightcone is that for a tangent vector with $(u_t, u_x)$, the class of null vectors is

$$-(1-v_s^2) u_t^2 - 2v_s u_x u_t + u_x^2 = 0$$

This is a quadratic equation in $u_x$ with solution

$$u_x = u_t (v_s \pm 1)$$

If the entire spacetime had this slant, this would not change anything, as it would just be diffeomorphic to Minkowski space, by the coordinate change $x \to x + v_st$. Only the fact that a region of a different slant is present gives the Alcubierre metric its properties.

If we consider the (slightly physically irrealistic) scenario of a bubble with $v_s = 0$, and an infinitely thin wall, then take the geodesic with tangent vector $(1, v, 0, 0)$. For now we'll ignore what happens exactly at the interface between the inside and the outside of the bubble. The geodesic coordinates are, if it starts at $\tau = 0$ at the piont $(0,-R,0,0)$

\begin{eqnarray} t(\tau) &=& \tau\\ x(\tau) &=& v\tau - R\\ \end{eqnarray}

This curve will reach the other side of the bubble $x = R$ at $\tau = 2R / v$, for a total time of

$$\Delta \tau = \int_0^{2R/v} \sqrt{- (1 - v_s^2) - 2 v_s v + v^2} d\tau = 2 R \sqrt{1 - (\frac{(1 - v_s^2)}{v^2} + 2 \frac{v_s}{v})}$$

As opposed to the usual time dilation formula in Minkowski space, if we set $v_s = 0$

$$\Delta \tau = 2 R \sqrt{1 - \frac{1}{v^2}} = 2\frac{R}{\gamma}$$

No matter the speed of the observer $v$, it is always possible to make the trip's duration arbitrarily small with the appropriate choice of the parameter $v_s$.

Along with this local tilting of the light cones, we also want the bubble itself to move, via the function $f$.

### Hiscock coordinates

In the case of a constant speed warp drive, $v_s(t) = v_s$, it is possible to redefine the metric in a spherically symmetric way, in a way similar to a Galilean transformation. Consider the coordinate transformation

$$r = x - v_s t$$

### Causality

By itself, the Alcubierre warp metric doesn't violate causality, despite its similarities to tachyons. This is easiest to see in the case of the Hiscock coordinates, since a spherically symmetric spacetime on $\mathbb{R}^n$ is always causal. This is actually very much like the tachyon case, since free tachyons in flat space will still only intersect the spacelike hypersurface once (except for the tachyon of infinite speed, and the same applies for warp bubbles).

But just as the case of tachyons, a system of warp bubbles will be able to violate causality. Consider the Lorentz boosted Alcubierre metric

$$g_{\mu\nu} = {\Lambda^{\mu'}}_{\mu} {\Lambda^{\nu'}}_{\nu} g_{\mu'\nu'}$$

## 4. The Krasnikov tunnel

Unlkike the Alcubierre warp drive, the Krasnikov tunnel only sland the light cone in one direction, the opposite direction to the first travel.

\begin{eqnarray} ds^2 &=& -(dt - dx) (dt + k(x,t) dx)\\ &=& -dt^2 + (1 + k(x,t)) dx dt + k(x,t) dx^2 \end{eqnarray} $$k(x,t) = 1 - (2 - \delta) \theta_\varepsilon (t-x) [\theta_\varepsilon(x) - \theta_\varepsilon(x + \varepsilon - D)]$$ $$\theta_\varepsilon(x) = \begin{cases} 1 & x > \varepsilon\\ 0 & x < 0 \end{cases}$$

The metric cannot be static here : in the case where the tunnel has always existed

$$ds^2 = -(dt - dx) (dt + k(x) dx)$$

It is possible to simply rescale this metric locally via $x \to \int k(x) dx$

Before the creation of the tunnel, at $t \ll 0$, any causal curve will travel in a region isometric to Minkowski space, meaning that a trip between $x = 0$ and $x = D$ and back will take at least

$$\Delta t = 2 \frac{|D - 0|}{c}$$

The ship will leave Earth at a time $t_1$ and return at a time $t_2 > t_1 + 2D/c$ with the proper time depending as usual on the time dilation formula. On the other hand, after the creation of the tunnel, the travel time will be

$$\Delta t = \int$$

### In $4$ dimensions

The Krasnikov metric generalizes easily to any number of dimension, by considering cylindrical coordinates with $z = 0$, $\rho = 0$ for the origin and $z = D$, $\rho = 0$ for the destination. In $4$ dimensions, this corresponds to the metric

$$ds^2 = -dt^2 + (1 - k(t, x, \rho)) dx dt + k(t,x,\rho) dx^2 + d\rho^2 + \rho^2 d\varphi^2$$

With the function

$$k(t,x,\rho) = 1 - (2 - \delta) \theta_\varepsilon (\rho_{max} - \rho) \theta_\varepsilon(t - x - \rho)[\theta_\varepsilon(x) - \theta_\varepsilon(x + \varepsilon - D)]$$

Like the two dimensional case, the function $k$ is $1$ well inside the region of the tunnel (a cylinder of length $D$ and radius $\rho_{max}$).

### Causality of the Krasnikov tube

The causality of the two-dimensional case is fairly easy to decide, as any simply connected two-dimensional spacetime is stably causal[6]. If the spacetime is at least of dimension $4$, it is possible to consider a case where we superpose at least two tunnels going to opposite directions with their ends roughly in the same region. This was impossible in two dimensions due to the fact that two tunnels would be unable to go from and to the same region without intersecting.

## Bibliography

1. Wormholes, warp drives and energy conditions
2. Miguel Alcubierre, The warp drive: hyper-fast travel within general relativity, 1994
3. Sergei Krasnikov, Hyperfast interstellar travel in general relativity, 1998
4. Sergei Krasnikov, What is faster -- light or gravity?, 2015
5. Allen E. Everett, Thomas A. Roman, A Superluminal Subway: The Krasnikov Tube, 2015
6. E. Minguzzi, M. Sanchez , The causal hierarchy of spacetimes, 2006

Last updated : 2018-03-30 14:13:19
Tags : general-relativity , warp-drive


text:
# How do you solve 3( m + 8) - 5m > - 2?

May 2, 2018

$m < 13$

#### Explanation:

$\text{distribute parenthesis}$

$3 m + 24 - 5 m > - 2$

$\Rightarrow - 2 m + 24 > - 2$

$\text{subtract 24 from both sides}$

$- 2 m \cancel{+ 24} \cancel{- 24} > - 2 - 24$

$\Rightarrow - 2 m > - 26$

$\text{divide both sides by } - 2$

$\textcolor{b l u e}{\text{remember to reverse the inequality sign}}$

$\Rightarrow m < 13 \text{ is the solution}$

$m \in \left(- \infty , 13\right) \leftarrow \textcolor{b l u e}{\text{in interval notation}}$

format: plain


text:
# Talk:Bayesian statistics

Jump to: navigation, search

reviewer A sent comments to the authors directly.

The link to the Wikipedia article for the phrase "a probability distribution" is broken and the word "a" should not be part of the text. It should be:
"a probability distribution"


text:
BWA mem running extremely slow
1
0
Entering edit mode
3.5 years ago
berge2015 ▴ 90

An unusual problem regarding bwa alignment has been bugging me for about a week which I have not been able to troubleshoot. If anyone can help me resolve this, I'll ask Santa to get you 3 kegs of beer!

I work with two plant species -- A & B -- and both have reference genomes. Ref seq sizes are ~11 and 14 Gbp for A and B, respectively. I indexed both references using ~/bwa-0.7.16a/bin/bwa index A_ref_seq.fa and the output looks normal.

Also from both species, I have few hundred individuals that were sequenced using Illumina as we want to do multi-sample SNP calling. Number of sequences in the fastq files vary of course but all have an average Q score of > 30, and their length is 90-95 bp. I have not seen anything unusual in the fq files for individuals from both species.

A couple of weeks ago, I aligned all individuals from A with A_ref_seq: ~/bwa-0.7.16a/bin/bwa mem -t 16 A_ref_seq.fa A_Ind1.fq > A_Ind1.sam

This went smoothly. To write sam file for each individual fq file, bwa took 4-5 minutes, on avereage. After this, I did sam to bam, sort bam, then mpileup for SNP calling (version 1.6 for both samtools and bcftools). All ran fine, no problems at all.

However, when I did bwa mem with individuals of species B last week, bwa took almost 2 hours for a fq file with roughly 1.3 million reads!! I am using same software version, same number of threads (16), same memory (24 gigs) and yet the time it takes is astronomically high! The sam outputs from B individuals are of similar size to the A individuals, so not like bwa is writing junk during the several hours it takes to churn out one sam file.

What could be the reason? And what can I do to make this go faster?

For troubleshooting, I tried making a new index, created new fastq files, but nope, the problem persists. I even moved the storage area where I was doing this ("scratch" vs. home directory) but this did not help. If I run the pipeline for species A right now, it runs fast and works as expected which indicates that any hardware/software changes on our server is not causing this.

I would really appreciate any suggestions to improve this. Thank you.

alignment bwa sam • 2.8k views
1
Entering edit mode

Any chance you can allocate more memory? I'm guessing your 14Gbp reference will require just over 24gigs.

I had 5gig allocated for human genome and alignment was really slow. After I followed Heng's advice and ran with 6gig it was normal speed. 3.1 human reference/5.5 gig minimum allocation = 14 reference B / x minimum allocation x = 24.8 gigs min ^no idea if it is linear like that, but it seems like a good place to start.

0
Entering edit mode

After your suggestion (and reading your old post), I increased the memory to 32 GB and it still is as slow. I have decided for the time being to run multiple jobs in parallel to compensate for the slowness. While that's going, I will also play with increasing nodes, processors per node, memory, etc and report here if anything improves my situation. I still find it very bizarre that this is happening despite running really fast on another species of similar size.

Edit (12-13-2017): This morning I ran it again on a single node with 24 processors but asked 126 GB of memory. And it is printing one sam file every 2 minutes, on average. This is a tremendous speed boost, compared with previous speed of 1 file every 2 freaking hours!! Seems like more memory is the answer.

Thanks Robert! Beer coming your way! ;-)

0
Entering edit mode

You are using two different algorithms so can't directly compare the running times of the two (even if all the rest of the stuff is the same). See this for more: When and why is bwa aln better then bwa mem? and also this. Your libraries could also have very different characteristics, which will complicate things.

I'll ask Santa to get you 3 kegs of beer!

I'll only take one. Need to heave some for Santa.

0
Entering edit mode

I too would like to put my money on the weirdness of the libraries leading to goofy fq files but really have not seen anything so out of the ordinary to notice it. What's insane is that I've done this numerous times in the past with species B but have never seen such slow output.

My only solution to this might be to submit multiple parallel jobs to account for the slowness.

0
Entering edit mode

I was not referring to goofy data files but insert sizes, parts of the genome represented in that library etc. 2 h is not that bad. With 500M read datasets people wait for a full day even with multiple threads.

0
Entering edit mode
3.5 years ago
Hussain Ather ▴ 960

The first time bwa runs on a species it must create the index, and that's very time-consuming.

0
Entering edit mode

I do not think that's the issue. Maybe for the first file, yes, but not for all subsequent files. As I wrote above, each file is taking hours in my case. Besides, it runs pretty fast for the first species and I get 10-15 sam outputs for individuals from species A.


text:
# American Institute of Mathematical Sciences

• Previous Article
LS-SVM approximate solution for affine nonlinear systems with partially unknown functions
• JIMO Home
• This Issue
• Next Article
A time-dependent scheduling problem to minimize the sum of the total weighted tardiness among two agents
April  2014, 10(2): 613-620. doi: 10.3934/jimo.2014.10.613

## The inverse parallel machine scheduling problem with minimum total completion time

 1 Department of Mathematics, East China University of Science and Technology, Shanghai 200237, China

Received  July 2012 Revised  May 2013 Published  October 2013

In inverse scheduling problems, a job sequence is given and the objective is to determine the minimal perturbation to parameters, such as processing times or weights of jobs so that the given schedule becomes optimal with respect to a pre-selected objective function. In this paper we study the necessary and sufficient conditions for optimality of the total completion time problem on parallel machines and inverse scheduling problem of the total completion time objective on parallel machines in which the processing times are minimally adjusted, so that a given target job sequence becomes an optimal schedule.
Citation: Hongtruong Pham, Xiwen Lu. The inverse parallel machine scheduling problem with minimum total completion time. Journal of Industrial and Management Optimization, 2014, 10 (2) : 613-620. doi: 10.3934/jimo.2014.10.613
##### References:
 [1] R. K. Ahuja and J. B. Orlin, Inverse optimization, Operations Research, 49 (2001), 771-783. doi: 10.1287/opre.49.5.771.10607. [2] Mokhatar S. Bazaraa, Hanif D. Sherali and C. M. Shetty, Nonlinear Programming: Theory and Algorithms, Third edition, Wiley-Interscience [John Wiley & Sons], Hoboken, NJ, 2006. doi: 10.1002/0471787779. [3] P. Brucker, Scheduling Algorithms, Springer, Berlin, 2001. [4] P. Brucker and N. V. Shakhlevich, Inverse scheduling with maximum lateness objective, Journal of Scheduling, 12 (2009), 475-488. doi: 10.1007/s10951-009-0117-9. [5] P. Brucker and N. V. Shakhlevich, Inverse Scheduling: Two-Machine Flow-Shop Problem, Journal of Scheduling, 2009. doi: 10.1007/s10951-010-0168-y. [6] R. J. Chen, F. Chen and G. C. Tang, Inverse problems of a single machine scheduling to minimize the total completion time, Journal of Shanghai Second Polytechnic University, 22 (2005), 1-7. [7] D. Goldfar and A. Idnani, A numerically stable dual method for solving strictly convex quadratic program, Mathematical Programming, 27 (1983), 1-33. doi: 10.1007/BF02591962. [8] C. Heuberger, Inverse combinatorial optimization: A survey on problems, methods and results, Journal of Combinatorial Optimization, 8 (2004), 329-361. doi: 10.1023/B:JOCO.0000038914.26975.9b. [9] Y. W. Jiang, L. C. Liu and W. Biao, Inverse minimum cost flow problems under the weighted Hamming distance, European Journal of Operational Research, 207 (2010), 50-54. doi: 10.1016/j.ejor.2010.03.029. [10] C. Koulamas, Inverse scheduling with controllable job parameters, International Journal of Services and Operations Management, 1 (2005), 35-43. doi: 10.1504/IJSOM.2005.006316. [11] L. C. Liu and J. Z. Zhang, Inverse maximum flow problems under the weighted Hamming distance, Journal of Combinatorial Optimization, 12 (2006), 395-408. doi: 10.1007/s10878-006-9006-8. [12] L. Liu and Q. Wang, Constrained inverse min-max spanning tree problems under the weighted Hamming distance, Journal of Global Optimization, 43 (2009), 83-95. doi: 10.1007/s10898-008-9294-x. [13] X. T. Xiao, L. W. Zhang and J. Z. Zhang, On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems, Journal of Industrial and Management Optimization, 5 (2009), 319-339. doi: 10.3934/jimo.2009.5.319. [14] C. Yang, J. Zhang and Z. Ma, Inverse maximum flow and minimum cut problems, Optimization, 40 (1997), 147-170. doi: 10.1080/02331939708844306. [15] X. G. Yang and J. Z. Zhang, Some inverse min-max network problems under weighted $l_1$ and $l_\infty$ norms with bound constraints on changes, Journal of Combinatorial Optimization, 13 (2007), 123-135. doi: 10.1007/s10878-006-9016-6. [16] X. Yang and J. Zhang, Some new results on inverse sorting problems, Lecture Notes in Computer Science, 3595 (2005), 985-992. doi: 10.1007/11533719_99. [17] F. Zhang, T. C. Ng and G. C. Tang, Inverse scheduling: Applications in shipping, International Journal of Shipping and Transport Logistics, 3 (2011), 312-322. doi: 10.1504/IJSTL.2011.040800. [18] J. Z. Zhang and Z. H. Liu, A further study on inverse linear programming problems, Journal of Computational and Applied Mathematics, 106 (1999), 345-359. doi: 10.1016/S0377-0427(99)00080-1.

show all references

##### References:
 [1] R. K. Ahuja and J. B. Orlin, Inverse optimization, Operations Research, 49 (2001), 771-783. doi: 10.1287/opre.49.5.771.10607. [2] Mokhatar S. Bazaraa, Hanif D. Sherali and C. M. Shetty, Nonlinear Programming: Theory and Algorithms, Third edition, Wiley-Interscience [John Wiley & Sons], Hoboken, NJ, 2006. doi: 10.1002/0471787779. [3] P. Brucker, Scheduling Algorithms, Springer, Berlin, 2001. [4] P. Brucker and N. V. Shakhlevich, Inverse scheduling with maximum lateness objective, Journal of Scheduling, 12 (2009), 475-488. doi: 10.1007/s10951-009-0117-9. [5] P. Brucker and N. V. Shakhlevich, Inverse Scheduling: Two-Machine Flow-Shop Problem, Journal of Scheduling, 2009. doi: 10.1007/s10951-010-0168-y. [6] R. J. Chen, F. Chen and G. C. Tang, Inverse problems of a single machine scheduling to minimize the total completion time, Journal of Shanghai Second Polytechnic University, 22 (2005), 1-7. [7] D. Goldfar and A. Idnani, A numerically stable dual method for solving strictly convex quadratic program, Mathematical Programming, 27 (1983), 1-33. doi: 10.1007/BF02591962. [8] C. Heuberger, Inverse combinatorial optimization: A survey on problems, methods and results, Journal of Combinatorial Optimization, 8 (2004), 329-361. doi: 10.1023/B:JOCO.0000038914.26975.9b. [9] Y. W. Jiang, L. C. Liu and W. Biao, Inverse minimum cost flow problems under the weighted Hamming distance, European Journal of Operational Research, 207 (2010), 50-54. doi: 10.1016/j.ejor.2010.03.029. [10] C. Koulamas, Inverse scheduling with controllable job parameters, International Journal of Services and Operations Management, 1 (2005), 35-43. doi: 10.1504/IJSOM.2005.006316. [11] L. C. Liu and J. Z. Zhang, Inverse maximum flow problems under the weighted Hamming distance, Journal of Combinatorial Optimization, 12 (2006), 395-408. doi: 10.1007/s10878-006-9006-8. [12] L. Liu and Q. Wang, Constrained inverse min-max spanning tree problems under the weighted Hamming distance, Journal of Global Optimization, 43 (2009), 83-95. doi: 10.1007/s10898-008-9294-x. [13] X. T. Xiao, L. W. Zhang and J. Z. Zhang, On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems, Journal of Industrial and Management Optimization, 5 (2009), 319-339. doi: 10.3934/jimo.2009.5.319. [14] C. Yang, J. Zhang and Z. Ma, Inverse maximum flow and minimum cut problems, Optimization, 40 (1997), 147-170. doi: 10.1080/02331939708844306. [15] X. G. Yang and J. Z. Zhang, Some inverse min-max network problems under weighted $l_1$ and $l_\infty$ norms with bound constraints on changes, Journal of Combinatorial Optimization, 13 (2007), 123-135. doi: 10.1007/s10878-006-9016-6. [16] X. Yang and J. Zhang, Some new results on inverse sorting problems, Lecture Notes in Computer Science, 3595 (2005), 985-992. doi: 10.1007/11533719_99. [17] F. Zhang, T. C. Ng and G. C. Tang, Inverse scheduling: Applications in shipping, International Journal of Shipping and Transport Logistics, 3 (2011), 312-322. doi: 10.1504/IJSTL.2011.040800. [18] J. Z. Zhang and Z. H. Liu, A further study on inverse linear programming problems, Journal of Computational and Applied Mathematics, 106 (1999), 345-359. doi: 10.1016/S0377-0427(99)00080-1.
 [1] Bin Zheng, Min Fan, Mengqi Liu, Shang-Chia Liu, Yunqiang Yin. Parallel-machine scheduling with potential disruption and positional-dependent processing times. Journal of Industrial and Management Optimization, 2017, 13 (2) : 697-711. doi: 10.3934/jimo.2016041 [2] Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial and Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269 [3] Chengxin Luo. Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 71-77. doi: 10.3934/naco.2015.5.71 [4] Chuanli Zhao, Yunqiang Yin, T. C. E. Cheng, Chin-Chia Wu. Single-machine scheduling and due date assignment with rejection and position-dependent processing times. Journal of Industrial and Management Optimization, 2014, 10 (3) : 691-700. doi: 10.3934/jimo.2014.10.691 [5] Xianyu Yu, Dar-Li Yang, Dequn Zhou, Peng Zhou. Multi-machine scheduling with interval constrained position-dependent processing times. Journal of Industrial and Management Optimization, 2018, 14 (2) : 803-815. doi: 10.3934/jimo.2017076 [6] Reza Alizadeh Foroutan, Javad Rezaeian, Milad Shafipour. Bi-objective unrelated parallel machines scheduling problem with worker allocation and sequence dependent setup times considering machine eligibility and precedence constraints. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021190 [7] Leiyang Wang, Zhaohui Liu. Heuristics for parallel machine scheduling with batch delivery consideration. Journal of Industrial and Management Optimization, 2014, 10 (1) : 259-273. doi: 10.3934/jimo.2014.10.259 [8] Min Ji, Xinna Ye, Fangyao Qian, T.C.E. Cheng, Yiwei Jiang. Parallel-machine scheduling in shared manufacturing. Journal of Industrial and Management Optimization, 2022, 18 (1) : 681-691. doi: 10.3934/jimo.2020174 [9] Ji-Bo Wang, Bo Zhang, Hongyu He. A unified analysis for scheduling problems with variable processing times. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1063-1077. doi: 10.3934/jimo.2021008 [10] Güvenç Şahin, Ravindra K. Ahuja. Single-machine scheduling with stepwise tardiness costs and release times. Journal of Industrial and Management Optimization, 2011, 7 (4) : 825-848. doi: 10.3934/jimo.2011.7.825 [11] Alireza Goli, Taha Keshavarz. Just-in-time scheduling in identical parallel machine sequence-dependent group scheduling problem. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021124 [12] Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1795-1807. doi: 10.3934/jimo.2021044 [13] Si-Han Wang, Dan-Yang Lv, Ji-Bo Wang. Research on position-dependent weights scheduling with delivery times and truncated sum-of-processing-times-based learning effect. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022066 [14] Xingong Zhang. Single machine and flowshop scheduling problems with sum-of-processing time based learning phenomenon. Journal of Industrial and Management Optimization, 2020, 16 (1) : 231-244. doi: 10.3934/jimo.2018148 [15] Zhichao Geng, Jinjiang Yuan. Scheduling family jobs on an unbounded parallel-batch machine to minimize makespan and maximum flow time. Journal of Industrial and Management Optimization, 2018, 14 (4) : 1479-1500. doi: 10.3934/jimo.2018017 [16] Ping Yan, Ji-Bo Wang, Li-Qiang Zhao. Single-machine bi-criterion scheduling with release times and exponentially time-dependent learning effects. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1117-1131. doi: 10.3934/jimo.2018088 [17] Yunqiang Yin, T. C. E. Cheng, Jianyou Xu, Shuenn-Ren Cheng, Chin-Chia Wu. Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration. Journal of Industrial and Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323 [18] Chengwen Jiao, Qi Feng. Research on the parallel–batch scheduling with linearly lookahead model. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3551-3558. doi: 10.3934/jimo.2020132 [19] Xianzhao Zhang, Dachuan Xu, Donglei Du, Cuixia Miao. Approximate algorithms for unrelated machine scheduling to minimize makespan. Journal of Industrial and Management Optimization, 2016, 12 (2) : 771-779. doi: 10.3934/jimo.2016.12.771 [20] Tsuguhito Hirai, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Performance optimization of parallel-distributed processing with checkpointing for cloud environment. Journal of Industrial and Management Optimization, 2018, 14 (4) : 1423-1442. doi: 10.3934/jimo.2018014

2020 Impact Factor: 1.801


text:
In [1]:
from math import log
import numpy as np
import matplotlib.pyplot as plt
np.seterr(divide='ignore', invalid='ignore');
fftResolution = 1024

## Introduction¶

CIC filters are computationally efficient implementations of narrowband lowpass filters. They are particularly suited for use as an anti-aliasing filter when decimating or an anti-image filter when interpolating. CIC filters are well suited for implementation in FPGAs and ASICs as they only require addition and subtraction operations and not multiplication [1].

CIC filters have a non-flat passband and as such are typically used in combination with a FIR filter which compensates for the passband droop [2]. In both interpolation and decimation, the FIR filter operates at the lower sample rate allowing for efficient FIR implementations that can take advantage of time-sharing.

• [1] Lyons, R. Understanting Digital Signal Processing. Third Edition, pp. 550-565
• [2] Altera Corporation, Understanding CIC Compensation Filters. Application Note 455

## How do CIC filters work?¶

The best way to understand how a CIC filter works is to start with a simple moving average filter and gradually work towards the efficient implementation of a CIC filter. Additionally, while CIC filters are almost always used as part of a resampling operation it is best to initially analyse them purely as a single rate filter.

### Moving average filter¶

A D point moving average filter sums the current sample with the previous D-1 samples and multiplies the result by 1/D.

The magnitude of the frequency response of a moving average filter is given by: $$\left | H(\omega ) \right | = \frac{1}{D}\left | \frac{\sin \left ( \frac{\omega D}{2} \right )}{\sin \left ( \frac{\omega }{2} \right )} \right |$$

In [2]:
plt.figure(figsize=(12,4))
def movingAverageFreqResponse(D):
Hfunc = lambda w : np.abs( (np.sin((w*D)/2.0)) / (np.sin((w)/2.0)) ) * (1.0/D)
w = np.arange(fftResolution) * np.pi/fftResolution
H = np.array(list(map(Hfunc, w)))
plt.plot(w/(2*np.pi),(20*np.log10((H))), label="{} point moving average".format(D))

movingAverageFreqResponse(4)
movingAverageFreqResponse(8)
axes = plt.gca()
axes.set_ylim([-60,3])
plt.grid()
plt.legend()
plt.title('D Point Moving average Filter')
plt.xlabel('Normalised freq (2$\pi$ radians/sample)')
plt.ylabel('Filter Magnitude Response (dB)')
plt.show()

It can be seen that a moving average filter is a lowpass filter with a sinc like frequency response. The location of the first null is set by the number of points the moving average is calculated over. For a 4-point moving average filter there is a null at fs/4 and 2*fs/4 where fs is the sample rate. In general, there will be nulls at intervals of fs/D.

### Running sum filter¶

It can be seen that removing the multiplication by 1/D will cause there to be a gain of D, but otherwise the frequency response is unchanged. A moving average filter without the multiplication by 1/D is known as a running sum filter.

In [3]:
plt.figure(figsize=(12,4))
def runningSumFreqResponse(D):
Hfunc = lambda w : np.abs( (np.sin((w*D)/2.0)) / (np.sin((w)/2.0)) )
w = np.arange(fftResolution) * np.pi/fftResolution
H = np.array(list(map(Hfunc, w)))
plt.plot(w/(2*np.pi),(20*np.log10((H))), label="{}-point running sum".format(D))

movingAverageFreqResponse(8)
runningSumFreqResponse(8)
axes = plt.gca()
axes.set_ylim([-60,20])
plt.grid()
plt.legend()
plt.title('Moving average filter vs Running sum filter')
plt.xlabel('Normalised freq (2$\pi$ radians/sample)')
plt.ylabel('Filter Magnitude Response (dB)')
plt.show()

Both the moving average filter and the running sum filter require D-1 summations to compute each output sample. A recursive running sum filter performs the same operation but only needs to compute one addition and one subtraction per output sample.

It is relatively intuitive that this produces the same response as the regular running sum filter. The integrator at the output sums every sample that enters it, however left part of the filter (the comb) ensures that for every sample that is added to the integrator, D inputs later it will be subtracted from integrator. The integrator can be thought of as keeping track of the sum of what would have been inside the running sum window.

The filter is stable providing the additions and subtractions are performed exactly. It is for this reason that a recursive running sum filter, and as we will see later a CIC filter, will only work with fixed point maths; the errors introduced by floating point calculations would eventually accumulate in the integrator.

### CIC filter¶

As it turns out a recursive running sum filter is actually CIC filter of order 1.

#### Comb then integrator or integrator then comb?¶

Both the integrator and comb are linear time-invariant operations. This means we can swap the integrator and comb sections without changing the output. It is worth pointing out that with the integrator first the output of the integrator could be massive, but providing the system is implemented using 2-complement maths, and the bit widths are sufficient to hold the final output sample the integrator will simply wrap round without causing any issues. The bit widths required to implement a CIC filter will be covered later.

In [4]:
# NB The comb and integrator are implemented for clarity and not efficiency!
def comb(inData, D):
outData = []
delay = [0] * D
for sample in inData:
outData.append(sample - delay[-1])
delay = [sample] + delay
delay.pop()
return outData

def integrator(inData):
delay = 0
outData = []
for sample in inData:
y = delay + sample
outData.append(y)
delay = y
return outData

impulse = [1]+[0]*(fftResolution)
impulseResponse = integrator(comb(impulse, 8)) # Apply the comb with delay 8, then the integrator.
impulseResponse2 = comb(integrator(impulse),8) # Apply the integrator, then the comb with delay 8.
# Plot result
# Only plot the positive frequencies (-ive freqs are just an image of +ive)
xaxis = np.arange(fftResolution/2) * 0.5/(fftResolution/2)
plt.figure(figsize=(12,4))
plt.plot(xaxis,(20*np.log10(np.abs(np.fft.fft(impulseResponse))))[0:int(fftResolution/2)], label="Comb then Integrator")
plt.plot(xaxis,(20*np.log10(np.abs(np.fft.fft(impulseResponse2))))[0:int(fftResolution/2)],'--', label="Integrator then Comb")
axes = plt.gca()
axes.set_xlim([0,0.5])
axes.set_ylim([-25,20])
plt.grid()
plt.legend()
plt.title('CIC Frequency Response (Order = 1, D = 8)')
plt.xlabel('Normalised freq (2$\pi$ radians/sample)')
plt.ylabel('Filter Magnitude Response (dB)')
plt.show()

For optimisation reasons, which we will soon cover, when used for decimation the integration operation is performed first, followed by the comb. For interpolation the opposite is true with the comb operation coming first, followed by the integration.

#### Setting the delay (D) value¶

Typically if we wish to interpolate or decimate by a factor of R then D is set to an integer multiple of R, normally 1 or 2. By making sure that D is an integer multiple of R some optimisations can be made in the implementation of the CIC filter. Typically it is noted as D = M*R where M is called the differential delay.

In the graph below the filter response of a CIC filter is shown for when M is 1 and 2.

In [5]:
plt.figure(figsize=(12,4))
impulse = [1]+[0]*(fftResolution)
impulseResponse3 = np.array(comb(integrator(impulse), 8))/8 # Divided by 8 to normalise gain
impulseResponse4 = np.array(comb(integrator(impulse),16))/16 # Divided by 16 to normalise gain
# Plot result
xaxis = np.arange(fftResolution/2) * 0.5/(fftResolution/2)
plt.plot(xaxis,(20*np.log10(np.abs(np.fft.fft(impulseResponse3))))[0:int(fftResolution/2)], label="M=1, i.e. D = R = 8")
plt.plot(xaxis,(20*np.log10(np.abs(np.fft.fft(impulseResponse4))))[0:int(fftResolution/2)], label="M=2, i.e. D = 2*R = 16")
plt.plot([0.0625,0.0625],[-45,1], '--', label="Nyquist frequency after decimation by 8")
axes = plt.gca()
axes.set_xlim([0,0.5])
axes.set_ylim([-40,1])
plt.grid()
plt.legend()
plt.title('Wideband CIC Frequency Response (Order = 1)')
plt.xlabel('Normalised freq (2$\pi$ radians/sample)')
plt.ylabel('Normalised Filter Magnitude Response (dB)')
plt.show()

The vertical dotted line in the above graph shows the Nyquist frequency after a decimation by a factor of 8. After decimation everything to the right of the line will be aliased into the passband of the filter. The aliases will be attenuated according to the frequency response shown in the graph. If this filter was used for interpolation then everything to the left of the green line would appear imaged throughout the new bandwidth. The images would be attenuated according to the frequency response shown in the graph.

#### Increasing CIC Attenuation¶

It is often important to achieve as much attenuation as possible. The frequency response of an order-1 CIC filter would not be sufficient in many applications. The attenuation can be increased by increasing the CIC order.

With a CIC filter the order is increased by simply cascading additional integrator and comb sections. The number of integrators and combs must be equal. An order-1 CIC has one integrator and one comb, an order-2 has two integrators and two combs, etc.

The magnitude of the CIC filter frequency response of order N is given by: $$\left | H(\omega ) \right | = \left | \frac{\sin \left ( \frac{\omega M}{2} \right )}{\sin \left ( \frac{\omega }{2R} \right )} \right |^{N}$$

In [6]:
plt.figure(figsize=(12,4))
def plotCICResponse(R,M,N, widebandResponse=1):

Hfunc = lambda w : np.abs( (np.sin((w*M)/2.)) / (np.sin(w/(2.*R))) )**N

if widebandResponse:
# 0 to R*pi
w = np.arange(fftResolution) * np.pi/fftResolution * R
else:
# 0 to pi
w = np.arange(fftResolution) * np.pi/fftResolution

gain = (M*R)**N
xAxis = np.arange(fftResolution) / (fftResolution * 2)
magResponse = np.array(list(map(Hfunc, w)))
plt.plot(xAxis, 20.0*np.log10(magResponse/gain), label="N = {}, M = {}".format(N,M))

def plotConfig(title):
axes = plt.gca(); axes.set_xlim([0,0.5]); axes.set_ylim([-140,1])
plt.grid(); plt.legend()
plt.title(title)
plt.xlabel('Normalised freq (2$\pi$ radians/sample)')
plt.ylabel('Normalised Filter Magnitude Response (dB)')
plt.show()

# Plot 1
plt.figure(figsize=(12,4))
plotCICResponse(R=8,M=1,N=2)
plotCICResponse(R=8,M=1,N=3)
plotCICResponse(R=8,M=1,N=4)
plotCICResponse(R=8,M=1,N=5)
plt.plot([0.0625,0.0625],[-140,1], '--', label="Nyquist frequency after decimation by 8")
plotConfig("Wideband CIC Frequency Response (R=8, M = 1, Order = N)")
# Plot 2
plt.figure(figsize=(12,4))
plotCICResponse(R=8,M=2,N=2)
plotCICResponse(R=8,M=2,N=3)
plotCICResponse(R=8,M=2,N=4)
plotCICResponse(R=8,M=2,N=5)
plt.plot([0.0625,0.0625],[-140,1], '--', label="Nyquist frequency after decimation by 8")
axes = plt.gca(); axes.set_xlim([0,0.5]); axes.set_ylim([-140,1])
plotConfig("Wideband CIC Frequency Response (R=8, M = 2, Order = N)")
# Plot 3
plt.figure(figsize=(12,4))
plotCICResponse(R=8,M=1,N=2, widebandResponse=0)
plotCICResponse(R=8,M=1,N=3, widebandResponse=0)
plotCICResponse(R=8,M=1,N=4, widebandResponse=0)
plotCICResponse(R=8,M=1,N=5, widebandResponse=0)
plotCICResponse(R=8,M=2,N=2, widebandResponse=0)
plotCICResponse(R=8,M=2,N=3, widebandResponse=0)
plotCICResponse(R=8,M=2,N=4, widebandResponse=0)
plotCICResponse(R=8,M=2,N=5, widebandResponse=0)
plotConfig("Post decimation CIC Frequency Response (R=8)")

<matplotlib.figure.Figure at 0x27643f64898>

## Gain of a CIC¶

CIC filters have an inherent gain as a result of summing the D delayed samples. It is common to cancel out the gain after the CIC filter by multiplying by $\frac{1}{gain}$. Additionally, it is often possible to design the filter such that the gain is a power of two and can be cancelled using a binary right shift operation.

NB. This gain has been cancelled out in most of the plots above in order to make the plots easier to compare.

### Decimator¶

For a decimator the gain is given by:

$Gain = D^{N} = \left ( RM \right )^{N}$ where R = decimation factor, M = Differential delay, and N = CIC order

When implementing a CIC decimator the register size must be set according to the formula below or overflows errors will occur.

$registerWidth = inputDataWidth + \left \lceil N\log_{2}\left ( RM \right ) \right \rceil$

i.e. for a 16bit input word decimated by 8 with a CIC of order 3 and a differential delay of 1 the size of the registers used to store the integrator and comb data must be at least $16 + \left \lceil 3\log_{2}\left ( 8*1 \right ) \right \rceil = 25 bits$

### Interpolator¶

When interpolating, as a result of the zero padding, there is a gain of $\frac{1}{R}$ in addition to the gain of the CIC. As a result the gain of a CIC interpolator is given by:

$Gain = \frac{\left ( RM \right )^{N} }{R}$ where R = interpolation factor, M = Differential delay, and N = CIC order

When implementing a CIC interpolator the register size must be set according to the formula below or overflows errors will occur.

$registerWidth = inputDataWidth + \left \lceil \frac{N\log_{2}\left ( RM \right )}{R} \right \rceil$

## Implementing the CIC¶

Until now we have kept the resampler separate from the CIC filter in order to make analysis easier. The key advantage of CICs are their computational efficiency when resampling. In order to achieve this computational efficiency, it is possible to slide the resampler through the comb section of the CIC.

In the case of the decimator the down-sampler is moved back through the comb. A comb with a delay of D followed by a rate-R down-sampler will produce exactly the same results as a rate-R down-sampler followed by a comb with a delay of D/R. Since we set D to always be an integer multiple (M) of R, the delay can be set to: $\frac{D}{R} = \frac{RM}{R} = M$.

In the case of the interpolator the up-sampler is moved forwards through the comb. An rate-R up-sampler followed by comb with a delay of D will produce exactly the same results as a comb with a delay of D/R followed by a rate-R up-sampler. As with the decimator $\frac{D}{R} = \frac{RM}{R} = M$.

## CIC Compensation Filter¶

The magnitude of the CIC compensation filter should have the inverse response to the CIC within the desired passband. This is given by: $$\left | H(\omega ) \right | = RM^{N} \left | \frac{\sin \left ( \frac{\omega }{2R} \right )}{\sin \left ( \frac{\omega M}{2} \right )} \right |^{N}$$

Since CIC filters have a gain of $RM^{N}$ we multiply the inverse CIC response by $RM^{N}$ otherwise the compensation filter will compensate for the CIC filter's gain. While this may be desirable in some cases it is more common to round and truncate the output of the CIC to remove the gain and then apply the compensation filter.

CIC compensation filters are typically placed at the lower sample rate end of the filters. i.e. after the CIC filter in a decimator and before the CIC filter in an interpolator. This allows for a more efficient implementation of the compensation filter as in FPGA or ASIC designs due to time sharing of elements like multipliers.

The passband attenuation and the ideal compensation filters needed for several different CIC filters are shown below.

In [7]:
def plotCICCompFilter(R,M,N):
plt.figure(figsize=(12,4))
w = np.arange(fftResolution) * np.pi/fftResolution
xAxis = np.arange(fftResolution) / (fftResolution * 2)
Hcomp = lambda w : ((M*R)**N)*(np.abs((np.sin(w/(2.*R))) / (np.sin((w*M)/2.)) ) **N)
Hcic = lambda w : (1/((M*R)**N))*np.abs( (np.sin((w*M)/2.)) / (np.sin(w/(2.*R))) )**N

cicMagResponse = np.array(list(map(Hcic, w)))
cicCompResponse = np.array(list(map(Hcomp, w)))

# Multiply frequency responses is a convolution in the time domain
combine = cicCompResponse * cicMagResponse

plt.plot(xAxis, 20.0*np.log10(cicMagResponse), label="CIC Filter")
plt.plot(xAxis, 20.0*np.log10(cicCompResponse), label="Compensation Filter")
plt.plot(xAxis, 20.0*np.log10(combine), label="Combined Response")

axes = plt.gca(); axes.set_xlim([0,0.5]);
plt.grid(); plt.legend()
plt.title("Ideal CIC Compensation filter M={}, N={}".format(M,N))
plt.xlabel('Normalised freq (2$\pi$ radians/sample)')
plt.ylabel('Normalised Filter Magnitude Response (dB)')

plt.show()

plotCICCompFilter(R=8,M=1,N=3)
plotCICCompFilter(R=8,M=1,N=5)
plotCICCompFilter(R=8,M=2,N=3)
plotCICCompFilter(R=8,M=2,N=5)

It can be seen how combining the ideal CIC response with the ideal compensation filter will give a flat passband. However, in practice it is not a good idea to achieve a flat response across the full Nyquist bandwidth with certain CIC filter configurations.

From these graphs we can make several observations.

1. The larger N is the greater attenuation in the passband of the CIC.
2. The passband attenuation when using M > 1 is very significant. M > 1 should only be used is the bandwidth of the signal of interest is a small proportion that provided by the lower sample rate of the CIC.

Typically, the bandwidth over which a flat passband is required is less than the Nyquist bandwidth. A couple of examples are shown below:

In [8]:
def plotCICCompFilter(R,M,N, cutOff, yMin, yMax):
plt.figure(figsize=(12,4))
w = np.arange(fftResolution) * np.pi/fftResolution
xAxis = np.arange(fftResolution) / (fftResolution * 2)
Hcomp = lambda w : ((M*R)**N)*(np.abs((np.sin(w/(2.*R))) / (np.sin((w*M)/2.)) ) **N)
Hcic = lambda w : (1/((M*R)**N))*np.abs( (np.sin((w*M)/2.)) / (np.sin(w/(2.*R))) )**N

cicMagResponse = np.array(list(map(Hcic, w)))
cicCompResponse = np.array(list(map(Hcomp, w)))
# Stop band
cicCompResponse[int(fftResolution*cutOff*2):] = np.finfo(float).eps

# Multiply frequency responses is a convolution in the time domain
combine = cicCompResponse * cicMagResponse

plt.plot(xAxis, 20.0*np.log10(cicMagResponse), label="CIC Filter")
plt.plot(xAxis, 20.0*np.log10(cicCompResponse), label="Compensation Filter")
plt.plot(xAxis, 20.0*np.log10(combine), label="Combined Response")

axes = plt.gca(); axes.set_xlim([0,0.5]); axes.set_ylim([yMin,yMax])
plt.grid(); plt.legend()
plt.title("Ideal CIC Compensation filter M={}, N={}, Cutoff={}fs".format(M,N,cutOff))
plt.xlabel('Normalised freq (2$\pi$ radians/sample)')
plt.ylabel('Normalised Filter Magnitude Response (dB)')

plt.show()
plotCICCompFilter(R=8,M=1,N=3,cutOff=0.25,yMin=-10,yMax=10)
plotCICCompFilter(R=8,M=2,N=5,cutOff=0.25,yMin=-40,yMax=25)

### FIR Compensation Filter¶

CIC compensation filters are often implemented as FIR filters. The firwin2 function scipy can calculate FIR filter taps from an array of attenuation vs normalised frequency. This can be used to generate a filter with a profile matching that of a compensation filter.

In [9]:
from scipy.signal import firwin2
from scipy.signal import freqz

# Cut off is the cutOff as a fraction of the sample rate
# i.e 0.5 = nyquist frequency
def getFIRCompensationFilter(R,M,N,cutOff,numTaps,calcRes=1024):

w = np.arange(calcRes) * np.pi/(calcRes - 1)
Hcomp = lambda w : ((M*R)**N)*(np.abs((np.sin(w/(2.*R))) / (np.sin((w*M)/2.)) ) **N)
cicCompResponse = np.array(list(map(Hcomp, w)))
# Set DC response to 1 as it is calculated as 'nan' by Hcomp
cicCompResponse[0] = 1
# Set stopband response to 0
cicCompResponse[int(calcRes*cutOff*2):] = 0
normFreq = np.arange(calcRes) / (calcRes - 1)
taps = firwin2(numTaps, normFreq, cicCompResponse)
return taps

def plotFIRCompFilter(R,M,N,cutOff,taps, yMin, yMax, wideband=False):

plt.figure(figsize=(12,4))

if wideband:
interp = np.zeros(len(taps)*R)
interp[::R] = taps
freqs,response = freqz(interp)
else:
freqs,response = freqz(taps)

if wideband:
w = np.arange(len(freqs)) * np.pi/len(freqs) * R
else:
w = np.arange(len(freqs)) * np.pi/len(freqs)

Hcic = lambda w : (1/((M*R)**N))*np.abs( (np.sin((w*M)/2.)) / (np.sin(w/(2.*R))) )**N
cicMagResponse = np.array(list(map(Hcic, w)))

combinedResponse = cicMagResponse * response

plt.plot(freqs/(2*np.pi),20*np.log10(abs(cicMagResponse)), label="CIC Filter")
plt.plot(freqs/(2*np.pi),20*np.log10(abs(response)), label="Compensation Filter")
plt.plot(freqs/(2*np.pi),20*np.log10(abs(combinedResponse)), label="Combined Response")
axes = plt.gca(); axes.set_xlim([0,0.5]); axes.set_ylim([yMin,yMax])
plt.grid(); plt.legend()
plt.title("CIC Compensation filter M={}, N={}, Cutoff={}fs, Taps={}".format(M,N,cutOff,len(taps)))
plt.xlabel('Normalised freq (2$\pi$ radians/sample)')
plt.ylabel('Normalised Filter Magnitude Response (dB)')
plt.show()

taps = getFIRCompensationFilter(R=8,M=1,N=5,cutOff=0.25,numTaps=64);
print("Full Response")
plotFIRCompFilter(R=8,M=1,N=5,cutOff=0.25,taps=taps,yMin=-100,yMax=5)
print("Zoom in on passband ripple")
plotFIRCompFilter(R=8,M=1,N=5,cutOff=0.25,taps=taps,yMin=-0.2,yMax=0.2)

Full Response


text:
# Number of matrices with entries in $\{0,1,2\}$ with prescribed row and column sums

I want to count the number of $\ell_1\times\ell_2$ matrices with entries in $\{0,1,2\}$ and prescribed sum of entries for each row and column.

For example, there are three $2\times 2$ matrices with row and column sums equal to 2: $$\begin{pmatrix}2&0\\0&2\end{pmatrix},\begin{pmatrix}0&2\\2&0\end{pmatrix},\begin{pmatrix}1&1\\1&1\end{pmatrix}$$

There are 21 $3\times 3$ matrices with row and column sums equal to 2 - not listed here, but you can check in GAP using the following command:

gap> R:=Filtered(Tuples([0,1,2],3),r->Sum(r)=2);
gap> Q:=Filtered(Tuples(R,3),M->ForAll(TransposedMat(M),r->Sum(r)=2));
gap> Size(Q);

I also found a paper by Wang and Zhang (1997) for the number of matrices with entries in $\{0,1\}$ with prescribed row and column sums, so I am wondering how I can extend it to $\{0,1,2\}$.


text:
# LASER-INDUCED FLUORESCENCE IN KLi

Please use this identifier to cite or link to this item: http://hdl.handle.net/1811/20266

Files Size Format View
2001-TH-06.jpg 250.9Kb JPEG image

 Title: LASER-INDUCED FLUORESCENCE IN KLi Creators: Ross, A. J.; Martin, F.; Crozet, P.; Aubert-Frécon, M.; Kowalczyk, Pawel; Jastrzębski, Wlodzimierz; Pashov, A. Issue Date: 2001 Abstract: Laser-induced fluorescence spectra of the $B \rightarrow X$ system of the potassium-lithium molecule have been recorded on a Fourier transform interferometer. The molecules were excited with a tuneable, single-mode cw dye laser operating with Rhodamine 110 or Coumarine 6 dye, and the spectra recorded in the range $12500 - 18500 cm^{-1}$ at a resolution of $0.05 cm^{-1}$. Vibrational levels up to $v = 46$ are observed for the main isotopomer, $^{39}K^{7}Li$. Ground state energies have been fitted to a Dunham polynomial expansion, and also directly to a pointwise potential curve. Both approaches fit the data with a root-mean-square error of $0.005 cm^{-1}$. The data define the ground state potential curve accurately out to about 7 \AA. The dissociation energy of the ground state $D_{e}$ is estimated to be $D_{e} = 6216 \pm 2 cm^{-1}$, and the highest vibrational level $v_{max} = 50$ for the main isotopomer. Very weak transitions around $12600 cm^{-1}$ are tentatively assigned as bands of the $2 ^{3}\Sigma^{+} \rightarrow 1 ^{3}\Sigma^{+}$ transition, observed as collisionally induced fluorescence. URI: http://hdl.handle.net/1811/20266 Other Identifiers: 2001-TH-06


text:
# Domain and Range of a Graph

Graphs of functions can be used to determine the domain and range. The graphs give us an idea of which values of x and which values of y are being taken. Many times this can be enough to fully determine the domain and range. However, there will be times when we will have to use algebra to check or be more specific.

Here, we will learn how to determine the domain and range of a graph of a function. We will look at several examples to illustrate these ideas.

##### ALGEBRA

Relevant for

Learning to find the domain and range of a graph.

See examples

##### ALGEBRA

Relevant for

Learning to find the domain and range of a graph.

See examples

## How to find the domain and the range?

### Domain

We remember that the domain of a function is the set of all possible values of the independent variable. That is, the domain is the set of all values of x that will result in real values of y.

To find the domain, we must remember that:

• The denominator of a fraction cannot be equal to zero.
• The number under a square root cannot be a negative number.

We determine the domain by finding all the values of the independent variable that we can use and excluding the values that do not result in actual outputs of the function.

### Range

We remember that the range of a function is the set of all possible values of the dependent variable. That is, the range is the set of all values of y that result from using the domain as input.

The range can be determined by finding the maximum or minimum values of y. Also, we can substitute different values of x and analyze what kind of values of y we get. Graphs are particularly useful for determining the range.

## Examples of domain and range of a graph

### EXAMPLE 1

Find the domain and range of the function f that has the following graph:

Solution: We can see that the graph extends horizontally from -2 to 3, but the -2 is not included. Therefore, the domain is (-2, 3].

Also, we see that the graph extends vertically from 2 to -2, so the range is [-2, 2].

### EXAMPLE 2

The following graph represents the function $latex f(x)= \frac{1}{x + 5}$. Determine its range and domain.

Solution: We can see that the graph extends horizontally beyond what we can see on the graph, so we can assume that it extends from negative infinity to positive infinity.

However, we can see that the graph never has a value of x at 5, so we have to exclude this value from the domain. Therefore, the domain is all real numbers of x and $latex x \neq -5$.

Similarly, we see that the graph extends vertically beyond what we can see in the graph, so we say that it extends from negative infinity to positive infinity. Here, we see that the y-values never reach zero, so we exclude them from the range.

Therefore, the range is all real values of $latex f(x)$ and $latex f(x \neq 0)$.

### EXAMPLE 3

The following graph represents the function f (x) = {{x} ^ 2} +5. Determine its range and domain.

Solution: This is a quadratic graph, so it stretches horizontally from negative infinity to positive infinity. That means that the domain is all real numbers of x.

We also see that the graph extends vertically from 5 to positive infinity. Therefore, the range is all real numbers of y and $latex y≥5$.

### EXAMPLE 4

The following is the graph of the function $latex \sqrt{-t+2}$. What is its domain and its range?

Solution: We see that the function extends indefinitely to the left and takes values up to 2. Then, its domain is all real numbers of t, where $latex t \leq 2$.

In the case of the range, we see that the function only takes positive values and extends upwards indefinitely. Therefore, the range is all real numbers of $latex f(t)$ and $latex f(t)≥0$.

### EXAMPLE 5

Find the domain and range of the following function:

Solution: We can see that this function has horizontal values that start at $latex x=-2$ and extend indefinitely to the right. However, we see that the function has an asymptote at $latex x=3$, that is, the function never takes that value.

Therefore, the domain of the function is all real numbers of x, where $latex x \geq -2$ and $latex x \neq 3$.

In the case of the range, we see that the graph extends from negative infinity to positive infinity. We also see that, although it seems that the graph never results in $latex y= 0$, we can see that the function takes this value at the point $latex x=-2$.

Therefore, the range of the function is all real numbers in y.


text:
Equipped with the right applications, a computer can be of great help in virtually any domain of activity. When it comes to designing and precision, no other tool is as accurate as a computer. Moreover, specialized applications such as AutoCAD give you the possibility to design nearly anything ranging from art, to complex mechanical parts or even buildings.
Suitable for business environments and experienced users
After a decent amount of time spent installing the application on your system, you are ready to fire it up. Thanks to the office suite like interface, all of its features are cleverly organized in categories. At a first look, it looks easy enough to use, but the abundance of features it comes equipped with leaves room for second thoughts.
Create 2D and 3D objects
You can make use of basic geometrical shapes to define your objects, as well as draw custom ones. Needless to say that you can take advantage of a multitude of tools that aim to enhance precision. A grid can be enabled so that you can easily snap elements, as well as adding anchor points to fully customize shapes.
With a little imagination and patience on your behalf, nearly anything can be achieved. Available tools allow you to create 3D objects from scratch and have them fully enhanced with high-quality textures. A powerful navigation pane is put at your disposal so that you can carefully position the camera to get a clearer view of the area of interest.
Various export possibilities
Similar to a modern web browser, each project is displayed in its own tab. This comes in handy, especially for comparison views. Moreover, layouts and layers also play important roles, as it makes objects handling a little easier.
Sine the application is not the easiest to carry around, requiring a slightly sophisticated machine to properly run, there are several export options put at your disposal so that the projects itself can be moved around.
Aside from the application specific format, you can save as an image file of multiple types, PDF, FBX and a few more. Additionally, it can be sent via email, directly printed out on a sheet of paper, or even sent to a 3D printing service, if available.
To end with
All in all, AutoCAD remains one of the top applications used by professionals to achieve great precision with projects of nearly any type. It encourages usage with incredible offers for student licenses so you get acquainted with its abundance of features early on. A lot can be said about what it can and can't do, but the true surprise lies in discovering it step-by-step.

## AutoCAD 20.0 Crack Activation Code With Keygen

AutoCAD is used for designing and drafting. At its simplest, it is for creating 2D vector graphics drawings. It can also be used to create design drawings for 3D models (architectural, mechanical, electrical, etc.), and animations, to create and edit text documents (technical reports, business reports, etc.), to create presentation graphics, and more. It is used by professionals, hobbyists, students, and corporations in different industries, in countries around the world. It is a powerful and very robust tool. AutoCAD is available in both “on-premise” and “cloud” configurations. “On-premise” refers to AutoCAD on a computer connected to the Internet. “Cloud” refers to AutoCAD being accessible via the Internet.

What is a Vector Graphics?

Vector graphics are images in a coordinate space where the entire image is a line, a curve, or other geometric form. Vector graphics are easier to create than bitmapped graphics, but are not as versatile as bitmapped graphics. Vector graphics are represented as mathematical equations and may be scaled to any size without loss of quality. You can view, modify, and create vector graphics in a variety of graphics applications and on the Web.

AutoCAD is a very powerful and versatile tool. Its strength lies in its ability to create, edit, and modify vector graphic images. You can use AutoCAD to make professional-quality drawings that you can then share, publish, print, or export. AutoCAD is a very powerful tool, but it is also very easy to use. You will be able to create any type of drawing you need for your project. Most of the more common drawing types will be described in the following sections. A few more advanced drawing types will also be described.

The following describes the steps you take to prepare a drawing and then creates a drawing.

2. Now, you will prepare the drawing area, by either selecting

AutoCAD has a direct support for other products such as BIM 360, Cimatron, DGN, GTA, X_DIRECT, CAM, CAM_DIRECT, CAM_MANAGER and many more.

Cimatron
CAM
CAM_DIRECT
CAM_MANAGER
AutoLISP
Visual LISP

References

Category:Computer-aided design software
Category:Computer-aided design software for Windows
Category:AutoLISP
Category:Microsoft Windows graphics-related softwareQ:

Why $f_n(x) = \sin nx$ doesn’t converge to $0$ at every point?

Consider $f_n(x) = \sin nx$ for $x \in \mathbb{R}$. Why do we say that this sequence does not converge to $0$ at every point?
I mean if $f_n(x) \to 0$ as $n \to \infty$ for some $x$ what is $f_n(x)$ for $x = 0$? How can we define $f_n$ at the point $0$?

A:

The sequence $(f_n)_{n\geq 1}$ converges to $0$ at all points $x$ such that $\lim_{n\to \infty} \sin(nx)=0$ by definition.
Thus, $f_n(0) =0$ for all $n\geq 1$, but $\sin(nx)=1$ for $n\in\{1,2,\dots\}$ so that $f_n(0)=1$ for all $n\geq 1$.

A:

If we define a sequence to converge to a point $\mathbf{x}$ iff the limit $\lim_{n\to\infty} \,f_n(x)=\lim_{n\to\infty} \,f_n(y)$ exists for all $x,y$ and the latter limit is $f(\mathbf{x})$, then the limit of $f_n(x)$ exists for all $x$ but is $\mathbf{0}$.
When we say “does not
ca3bfb1094

## AutoCAD 20.0 Crack + With Serial Key

Select a required component by pressing ctrl+a. The key is also
displayed in the menu. Press ctrl+shift+a (ctrl+shift+space by default)
to access the components’ info dialog. The components are displayed
in the right column. In the following example, there are both a box and
a symbol in the left column.

When pressing ctrl+shift+a in the dialogue box, the same components
are displayed in the right column. The components can be dragged to the
canvas. Use ctrl+a (normally the key to add objects) to add a box to the
object list. To add a symbol, use ctrl+shift+a. Drag the box to the
symbol and select it. The symbol will be drawn within the box.

If the option to add component settings is selected, the parameters
of the component will be drawn in the current dialog.

When selecting the canvas on which to draw the component, a dotted
line will appear at the selected point. Clicking the line will add the
selected point. Double clicking will clear the line.

Press alt+d to deselect all components, select a component by pressing
ctrl+a, and so on.
some effect on the outcome of court proceedings. In the ordinary course of events, judicial economy and judicial efficiency may be promoted by limiting the number of witnesses required to prove up a complaint or counterclaim which plaintiff seeks to have adjudicated. However, when a party seeks to have an entire document, or a portion of a document, entered in evidence as an exhibit at trial, the trial court is in a far different position when considering the matter. The particular documents in question must be identified, their content summarized or summarized for the court by the party seeking to introduce them, and the source of the documents or the source of the summary must be disclosed, so that the court may satisfy itself of the authenticity of the documents and of their relevance to the proceedings in question. This the defendant was not required to do in the instant case.

III.

27
We think that the court below did not abuse its discretion in dismissing the defendant’s counterclaim. If the defendant’s fraud and misrepresentation, under which count she sought to recover damages, had been set out in the plaintiff’s complaint, her claim might have been within the statute. In fact, the plaintiff herself dealt with the defendant upon the mistaken belief that the defendant was a licensed real

## What’s New In?

Draw smarter by using digital ink with the new text feature, AutoText. It’s the perfect tool for quickly jotting notes on design data while drawing.

New tools for BIM-integration and construction

Work with BIM to streamline and streamline the way you work, incorporating your BIM models and designs into AutoCAD right on the go.

Get the latest in construction technology and bring the same 3D-like style and touch functionality to the CAD application.

Make a design complete with new command that allows you to place a 3D object onto a file layer.

Change the way you view your drawing by using multiple views and camera tools.

Drawing commands that are no longer optimized for mechanical drafting have been removed.

View or move drafting objects on their own layer to better manage your designs.

A better simulation engine and the ability to create 3D curves and surfaces, allowing you to more easily and accurately simulate the design of 3D objects.

Pagination is back, automatically providing the paper size and orientation for your most-recently used document.

Find the commands you need quickly. New commands are always available in the command bar.

Accuracy and speed:

Evaluate accuracy at any time, and view an accurate color-independent display of your drawing for a clear view.

Reduce the number of drawing steps.

Draw with speed and accuracy using a new live feature that allows you to draw and measure with the cursor, or place points and connectors automatically.

Access design performance data and analyze performance using the new Performance Analysis Wizard.

Automatic change tracking that tracks the last-used file and works with the simulation engine for the most accurate redraw.

Save changes to the same drawing layer as the original drawing.

Access previous drawings and diagrams for faster design review.

A new diagram-oriented default toolbars that makes it easy to get started.

Collaboration:

Improve communication in your organization, regardless of the collaboration platform used.

Sync with the latest design from the cloud, and receive real-time feedback.

Share your designs, parts, and drawings with your team and collaborators using Teamwork, a new and improved collaboration platform


text:
Math Help - Show a group is isomorphic. Table included!

1. Show a group is isomorphic. Table included!

Let T be the group with four elements e,x,y,z with multiplication table

lllll | e | x | y | z |
l e | e | x | y | z |
l x | x | e | z | y |
l y | y | z | x | e |

l z | z | y | e | x |

Show that this group is isomorphic to Z4.
(Z being all integers)
(e being the identity)

I know I have to define a bijection between these groups which is a homomorphism but then I'm lost.

2. Re: Show a group is isomorphic. Table included!

Z4 is cyclic of order 4. in Z4, 1 is an element of order 4 which generates the group (3 is also a generator).

if T and Z4 are to be isomorphic, T has to have an element of order 4.

well, it's not e, that just leaves 3 to check. what is the order of x?

x^2 = e, so x is of order 2. let's keep looking.....

y^2 = x. this looks promising....

y^3 = (y^2)y = xy = z. so y is not of order 1,2 or 3...what's left? just to be sure, let's check:

y^4 = (y^3)y = zy = e, so yep, y is of order 4.

a homomorphism has to map identity to identity:

so e--->0 is already chosen for us.

an isomorphism has to send elements to images of the same order, so we have two choices for y:

y-->1, or y-->3. let's pick y--->1. we can now write T as {e,y,y^2,y^3} (since we know y^2 = x, and y^3 = z)

now, convince yourself that sending y^k <---> k (mod 4) is an isomorphism.

the bijection part is easy...why is it a homomorphism (can you think of a way to prove it "in general" without verifying all 16 possible products in T)?

3. Re: Show a group is isomorphic. Table included!

Originally Posted by Deveno
Z4 is cyclic of order 4. in Z4, 1 is an element of order 4 which generates the group (3 is also a generator).

if T and Z4 are to be isomorphic, T has to have an element of order 4.

well, it's not e, that just leaves 3 to check. what is the order of x?

x^2 = e, so x is of order 2. let's keep looking.....

y^2 = x. this looks promising....

y^3 = (y^2)y = xy = z. so y is not of order 1,2 or 3...what's left? just to be sure, let's check:

y^4 = (y^3)y = zy = e, so yep, y is of order 4.

a homomorphism has to map identity to identity:

so e--->0 is already chosen for us.

an isomorphism has to send elements to images of the same order, so we have two choices for y:

y-->1, or y-->3. let's pick y--->1. we can now write T as {e,y,y^2,y^3} (since we know y^2 = x, and y^3 = z)

now, convince yourself that sending y^k <---> k (mod 4) is an isomorphism.

the bijection part is easy...why is it a homomorphism (can you think of a way to prove it "in general" without verifying all 16 possible products in T)?

Can this be proven by figuring the table out?
T' =

lllll | 0 | 1 | 2 | 3 |
l 0 | 0 | 1 | 2 | 3 |
l 1 | 1 | 2 | 3 | 0 |
l 2 | 2 | 3 | 0 | 1 |
l 3 | 3 | 0 | 1 | 2 |

A homomorphism between T and T' is any function, f, satisfying f(a*b) = f(a)*f(b) for all a,b in T

For this table (T'), f(2*3) = f(1) vs f(2) * f(3) = f(1), right?

which is the same for T which would be:
f(y*z) = f(x) vs f(y) * f(z) = f(x), right?

4. Re: Show a group is isomorphic. Table included!

yes, you CAN compare tables....but that approach will prove useless with any group of large size (even a group of order 12 takes more time to construct a table than most people are willing to do).

but behold! here is my "magic proof"

define φ(y^k) = k (mod 4). we already have seen this is a bijection.

φ((y^k)(y^m)) = φ(y^(k+m)) = k+m (mod 4) = k (mod 4) + m (mod 4) = φ(y^k) + φ(y^m), no muss, no fuss, φ is a homomorphism.

5. Re: Show a group is isomorphic. Table included!

Originally Posted by Deveno
yes, you CAN compare tables....but that approach will prove useless with any group of large size (even a group of order 12 takes more time to construct a table than most people are willing to do).

but behold! here is my "magic proof"

define φ(y^k) = k (mod 4). we already have seen this is a bijection.

φ((y^k)(y^m)) = φ(y^(k+m)) = k+m (mod 4) = k (mod 4) + m (mod 4) = φ(y^k) + φ(y^m), no muss, no fuss, φ is a homomorphism.

Wow! That proof is delightful. Thank you! Certainly too cool to be in my textbook.


text:
## Essential University Physics: Volume 1 (4th Edition) Clone

Published by Pearson

# Chapter 10 - Section 10.3 - Rotational Inertia and the Analog of Newton’s Law - Example - Page 181: 10.5

#### Answer

$\frac{1}{12}ML^2$

#### Work Step by Step

We solve an integral to find: $I = \int r^2 dm = \int_{-L/2}^{L/2}x^2 \frac{M}{L}dx = \frac{1}{12}ML^2$

After you claim an answer you’ll have 24 hours to send in a draft. An editor will review the submission and either publish your submission or provide feedback.